fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. const int MAXN = 2e3 + 7;
  5. int par[MAXN][27], f[MAXN][27], h[MAXN], n, m, q;
  6. vector <pair<int, int>> a[MAXN];
  7.  
  8. void dfs(int u, int p){
  9.     for(auto [v, w] : a[u]){
  10.         if(v != p){
  11.             f[v][0] = w;
  12.             par[v][0] = u;
  13.             h[v] = h[u] + 1;
  14.             dfs(v, u);
  15.         }
  16.     }
  17. }
  18.  
  19. void precompute(){
  20.     for(int j = 1; j <= 20; j++)
  21.         for(int i = 1; i <= n; i++){f[i][j] = f[i][j - 1] + f[par[i][j - 1]][j - 1]; 
  22.             par[i][j] = par[par[i][j - 1]][j - 1];
  23.     }
  24. }
  25.  
  26. int lca(int u, int v){
  27.     int ans = 0;
  28.     if(h[u] < h[v]) swap(u, v);
  29.     int x = h[u] - h[v];
  30.     for(int i = 30; i >= 0; i--){
  31.         if(x >= (1 << i)){
  32.             ans += f[u][i];
  33.             u = par[u][i];
  34.             x -= (1 << i);
  35.         }
  36.     }
  37.     if(u == v) return ans;
  38.  
  39.     int max_h = __lg(h[u]);
  40.  
  41.     for(int i = max_h; i >= 0; i--){
  42.         if(par[u][i] != par[v][i]){
  43.             ans += f[u][i];
  44.             ans += f[v][i];
  45.             u = par[u][i];  
  46.             v = par[v][i];
  47.         }
  48.     }
  49.     return ans + f[v][0] + f[u][0];
  50. }
  51.  
  52. int main(){
  53.     ios_base::sync_with_stdio(0);
  54.     cout.tie(0);
  55.     cin.tie(0);
  56.     cin >> n >> q;
  57.     for(int i = 1; i <= n - 1; i++){
  58.         int x, y, w;
  59.         cin >> x >> y >> w;
  60.         a[x].pb({y, w});
  61.         a[y].pb({x, w});
  62.     }
  63.     dfs(1, -1);
  64.     precompute();
  65.     while(q--){
  66.         int x, y;
  67.         cin >> x >> y;
  68.         cout << lca(x, y) << endl;
  69.     }
  70. }
  71.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9LtpQi
language:
C++14 (gcc 8.3)
created:
12 days 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!