fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set> 
  4. #include <map>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <iomanip>
  8. using namespace std;
  9. typedef long long int ll;
  10. ll dist[200000];
  11. vector <int> v[200000],w[200000];
  12. int parent[200000][20];
  13. int D[200000];
  14. int depth;
  15. void dfs(int x,int p){
  16.     depth++;
  17.     D[x]=depth;
  18.     int mx=log2(depth);
  19.     parent[x][0]=p;
  20.     for(int i=1;i<=mx;i++)parent[x][i]=parent[parent[x][i-1]][i-1];
  21.     for(int i=0;i<v[x].size();i++){
  22.         int node=v[x][i];
  23.         if(node==p)continue;
  24.         int weight=w[x][i];
  25.         dist[node]=dist[x]+weight;
  26.         dfs(node,x);
  27.     }
  28.     depth--;
  29. }
  30. int lca(int x,int y){
  31.     while(D[x]<D[y]){
  32.         int jump=log2(D[y]-D[x]);
  33.         y=parent[y][jump];
  34.     }
  35.     while(D[y]<D[x]){
  36.         int jump=log2(D[x]-D[y]);
  37.         x=parent[x][jump];
  38.     }
  39.     if(x==y)return y;
  40.     int mx=log2(D[x]);
  41.     for(int i=mx;i>=0;i--){
  42.         int px=parent[x][i];
  43.         int py=parent[y][i];
  44.         if(px!=py){
  45.             x=px;
  46.             y=py;
  47.         }
  48.     }
  49.     return parent[x][0];
  50. }
  51. ll distance(int a,int b){
  52.     return dist[a]-dist[b];
  53. }
  54. int main()
  55. {
  56.     ios_base::sync_with_stdio(false);
  57.     cin.tie(0);
  58.     int t;
  59.     scanf("%d",&t);
  60.     while(t--){
  61.         int n,q,r;
  62.         scanf("%d %d %d",&n,&q,&r);
  63.         for(int i=1;i<=n;i++){
  64.             v[i].clear();
  65.             w[i].clear();
  66.         }
  67.         for(int i=1;i<n;i++){
  68.             int a,b,c;
  69.             scanf("%d %d %d",&a,&b,&c);
  70.             v[a].push_back(b);
  71.             v[b].push_back(a);
  72.             w[a].push_back(c);
  73.             w[b].push_back(c);
  74.         }
  75.         depth=-1;
  76.         dist[1]=0;
  77.         dfs(1,0);
  78.         while(q--){
  79.             int u,v;
  80.             scanf("%d %d",&u,&v);
  81.             int l=lca(u,v);
  82.             ll ans=distance(u,l)+distance(v,l);
  83.             printf("%lld\n",ans);
  84.         }
  85.     }
  86.     return 0;
  87. }
Success #stdin #stdout 0s 13024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UJ8QuW
language:
C++14 (gcc 8.3)
created:
3 years 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!