ulvis.paste.net

Paste Search Dynamic
Recent pastes
tree
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<pair<long long,long long> >tree[10004];
  4. long long sparse[10004][20];
  5. bool vis[10004];
  6. long long n,l[10004],t[10004],dist[10004];
  7. void dfs(long long par,long long u,long long lev)
  8. {
  9.     l[u]=lev;
  10.     t[u]=par;
  11.     vis[u]=true;
  12.     for(long long i=0;i<tree[u].size();i++){
  13.         long long v=tree[u][i].first;
  14.         if(vis[v])continue;
  15.         dist[v]=dist[u]+tree[u][i].second;
  16.         dfs(u,v,lev+1);
  17.     }
  18. }
  19. void lcaBuild()
  20. {
  21.     //cout<<"jisan\n";
  22.     memset(sparse,-1,sizeof(sparse));
  23.     for(long long i=1;i<=n;i++){
  24.         sparse[i][0]=t[i];
  25.     }
  26.     for(long long j=1;j<20;j++){
  27.         for(long long i=1;i<=n;i++){
  28.             if(sparse[i][j-1]!=-1)
  29.                 sparse[i][j]=sparse[sparse[i][j-1]][j-1];
  30.         }
  31.     }
  32. }
  33. /*
  34. 1
  35.  
  36. 13
  37. 1 13 2
  38. 1 2 2
  39. 13 3 2
  40. 3 5 2
  41. 5 7 2
  42. 7 9 2
  43. 9 11 2
  44. 2 4 2
  45. 4 6 2
  46. 6 8 2
  47. 8 10 2
  48. 10 12 2
  49. */
  50. pair<long long,long long> lcaQuery(long long x,long long y){
  51.     long long lev=0,c=0;
  52.     if(l[x]<l[y])swap(x,y),c=1;
  53.     long long temp,i,log;
  54.  
  55.     log=1;
  56.     while(1){
  57.         temp=log+1;
  58.         if((1<<temp)>l[x])break;
  59.         log++;
  60.     }
  61.     for(i=log;i>=0;i--){
  62.         if(l[x]-(1<<i)>=l[y]){
  63.             x=sparse[x][i];
  64.             if(!c)lev+=(1<<i);
  65.         }
  66.     }
  67.     if(x==y)return make_pair(x,lev+1);
  68.     for(i=log;i>=0;i--){
  69.         if(sparse[x][i]!=-1 && sparse[x][i]!=sparse[y][i]){
  70.             lev+=(1<<i);
  71.             x=sparse[x][i],y=sparse[y][i];
  72.         }
  73.     }
  74.     return make_pair(t[x],lev+2);
  75. }
  76. int main()
  77. {
  78.     bool flag=false;
  79.     long long tc,i,j,x,y,w;
  80.     scanf("%lld",&tc);
  81.     pair<long long,long long>top;
  82.     while(tc--){
  83.         getchar();
  84.         scanf("%lld",&n);
  85.         for(i=1;i<n;i++){
  86.             scanf("%lld %lld %lld",&x,&y,&w);
  87.             tree[x].push_back(make_pair(y,w));
  88.             tree[y].push_back(make_pair(x,w));
  89.         }
  90.         string s;
  91.         memset(vis,false,sizeof(vis));
  92.         dist[1]=0;
  93.         dfs(1,1,0);
  94.         lcaBuild();
  95.         while(cin>>s,s!="DONE"){
  96.             cin>>x>>y;
  97.             flag=false;
  98.             top=lcaQuery(x,y);
  99.             if(s=="KTH"){
  100.                 cin>>w;
  101.                 long long l1,l2,log=1;
  102.                 if(w==top.second){cout<<top.first<<endl;flag=true;}
  103.                 else if(w>top.second){
  104.                     l2=l[y];
  105.                     long long temp=w-top.second;
  106.                     w=l[top.first]+temp;
  107.                 }
  108.                 else y=x,w=l[x]+1-w;
  109.                 if(!flag){
  110.                     while(1){
  111.                         long long val=log+1;
  112.                         if((1<<val)>w)break;
  113.                         log++;
  114.                     }
  115.                     for(i=log;i>=0;i--){
  116.                         if(l[y]-(1<<i) >=w)
  117.                             y=sparse[y][i];
  118.                     }
  119.                     cout<<y<<endl;
  120.                 }
  121.             }
  122.             else{
  123.                 j=dist[x]-dist[top.first];
  124.                 i=dist[y]-dist[top.first];
  125.                 cout<<j+i<<endl;
  126.             }
  127.         }
  128.         for(i=1;i<=n;i++)tree[i].clear();
  129.         cout<<endl;
  130.     }
  131.     return 0;
  132. }
Parsed in 0.028 seconds