fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 200000 + 5;
  5. const int LOG = 18;
  6. const int INF = 1e18;
  7.  
  8. vector<pair<int,int>> adj[N];
  9. int par[N][LOG];
  10. int mn[N][LOG], mx[N][LOG];
  11. int depth[N];
  12. int n, q;
  13.  
  14. /* DFS khởi tạo */
  15. void dfs(int u, int p, int w){
  16.     par[u][0] = p;
  17.     mn[u][0] = w;
  18.     mx[u][0] = w;
  19.  
  20.     for(auto [v, wt] : adj[u]){
  21.         if(v == p) continue;
  22.         depth[v] = depth[u] + 1;
  23.         dfs(v, u, wt);
  24.     }
  25. }
  26.  
  27. /* Build bảng nhảy */
  28. void build(){
  29.     for(int k = 1; k < LOG; k++){
  30.         for(int i = 1; i <= n; i++){
  31.             int p = par[i][k-1];
  32.             par[i][k] = par[p][k-1];
  33.             mn[i][k] = min(mn[i][k-1], mn[p][k-1]);
  34.             mx[i][k] = max(mx[i][k-1], mx[p][k-1]);
  35.         }
  36.     }
  37. }
  38.  
  39. /* Query min/max trên đường đi */
  40. pair<int,int> query(int u, int v){
  41.     int Min = INF, Max = 0;
  42.  
  43.     if(depth[u] < depth[v]) swap(u, v);
  44.  
  45.     // Đưa u lên cùng độ sâu với v
  46.     int diff = depth[u] - depth[v];
  47.     for(int k = 0; k < LOG; k++){
  48.         if(diff & (1 << k)){
  49.             Min = min(Min, mn[u][k]);
  50.             Max = max(Max, mx[u][k]);
  51.             u = par[u][k];
  52.         }
  53.     }
  54.  
  55.     if(u == v) return {Min, Max};
  56.  
  57.     // Nhảy song song lên LCA
  58.     for(int k = LOG - 1; k >= 0; k--){
  59.         if(par[u][k] != par[v][k]){
  60.             Min = min({Min, mn[u][k], mn[v][k]});
  61.             Max = max({Max, mx[u][k], mx[v][k]});
  62.             u = par[u][k];
  63.             v = par[v][k];
  64.         }
  65.     }
  66.  
  67.     // Bước cuối lên LCA
  68.     Min = min({Min, mn[u][0], mn[v][0]});
  69.     Max = max({Max, mx[u][0], mx[v][0]});
  70.  
  71.     return {Min, Max};
  72. }
  73.  
  74. int main(){
  75.     ios::sync_with_stdio(false);
  76.     cin.tie(nullptr);
  77.  
  78.     cin >> n >> q;
  79.     for(int i = 1; i < n; i++){
  80.         int u, v, w;
  81.         cin >> u >> v >> w;
  82.         adj[u].push_back({v, w});
  83.         adj[v].push_back({u, w});
  84.     }
  85.  
  86.     depth[1] = 0;
  87.     dfs(1, 0, INF);
  88.     build();
  89.  
  90.     while(q--){
  91.         int u, v;
  92.         cin >> u >> v;
  93.         auto res = query(u, v);
  94.         cout << res.first << " " << res.second << '\n';
  95.     }
  96.  
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0.01s 12348KB
comments (?)
stdin
copy 
5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2
stdout
copy 
0 0
0 0
https://ideone.com/ISXL6T
language:
C++14 (gcc 8.3)
created:
21 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!