fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int lli;
  4. #define pb push_back
  5. const lli mod=1e9+7;
  6. const lli mod1=998244353;
  7. #define fi first
  8. #define se second
  9. vector<pair<lli,lli> > v[100001];
  10. lli lca[100001][18];
  11. lli level[100001];
  12. lli sum[100001]={0};
  13. lli dfs(lli node,lli par,lli lev,lli sum1)
  14. {
  15.     level[node]=lev;
  16.     lca[node][0]=par;
  17.     sum[node]=sum[par]+sum1;
  18.     for(pair<lli,lli> child:v[node])
  19.     {
  20.         if(child.fi!=par)
  21.         dfs(child.fi,node,lev+1,child.se);
  22.     }
  23.     return 0;
  24. }
  25. int main()
  26. {
  27.     ios_base::sync_with_stdio(false);
  28.     cin.tie(NULL);
  29.     lli T;
  30.     cin>>T;
  31.     while(T--)
  32.     {
  33.         lli i,n,q,j,root;
  34.         cin>>n>>q>>root;
  35.         lli x=log2(n)+1;
  36.         lli p,r,w;
  37.         for(i=0;i<n-1;i++)
  38.         {
  39.             cin>>p>>r>>w;
  40.             v[r].pb({p,w});
  41.             v[p].pb({r,w});
  42.         }
  43.         for(i=1;i<=n;i++)
  44.         {
  45.             for(j=1;j<x;j++)
  46.             {
  47.                 lca[i][j]=-1;
  48.             }
  49.         }
  50.         dfs(root,0,0,0);
  51.         for(j=1;j<x;j++)
  52.         {
  53.             for(i=1;i<=n;i++)
  54.             {
  55.                 if(lca[i][j-1]!=-1)
  56.                 {
  57.                     lli par=lca[i][j-1];
  58.                     lca[i][j]=lca[par][j-1];
  59.                 }
  60.             }
  61.         }
  62.         lli b,c;
  63.         while(q--)
  64.         {
  65.             cin>>b>>c;
  66.             lli ans=sum[b]+sum[c];
  67.             if(level[b]>level[c]) swap(b,c);
  68.             lli d=level[c]-level[b];
  69.             lli r;
  70.             while(d>0)
  71.             {
  72.                 i=log2(d);
  73.                 c=lca[c][i];
  74.                 d-=(1<<i);
  75.             }
  76.             for(i=x-1;i>=0;i--)
  77.             {
  78.                 if(lca[c][i]!=-1 && lca[c][i]!=lca[b][i])
  79.                 {
  80.                     c=lca[c][i],b=lca[b][i];
  81.                 }
  82.             }
  83.             b=lca[b][0];
  84.             ans-=(2*sum[b]);
  85.             cout<<ans<<endl;
  86.         }
  87.         for(i=0;i<=n;i++)
  88.             v[i].clear(),level[i]=-1,sum[i]=0;
  89.     }
  90.     return 0;
  91. }
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
Runtime error #stdin #stdout 0s 5784KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0GtafV
language:
C++ (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!