fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
  3. using namespace std;
  4. const int N=10100;
  5. vector <int> edges[N], indices[N], cost[N];
  6. int baseArray[N], ptr;
  7. int chainNo, chainInd[N], chainHead[N], posInBase[N], indexx[N];
  8. int depth[N], parent[N][30], subtree[N], seg[4*N] ,bottomvertexofedge[N];
  9. int n;
  10.  
  11. // DFS Begin ---------------------------------------------------------------------------
  12. void dfs(int s,int p,int level){
  13.  
  14.     subtree[s]=1;
  15.     depth[s]=level;
  16.     parent[s][0]=p;
  17.     for(int bit=1;bit<15;bit++){
  18.         if(parent[s][bit-1]!=-1)      
  19.             parent[s][bit]=parent[parent[s][bit-1]][bit-1];
  20.     }
  21.  
  22.     for(int i=0;i<edges[s].size();i++){
  23.         int x=edges[s][i];
  24.         if(x==p)    continue;
  25.         bottomvertexofedge[indices[s][i]]=x;
  26.         dfs(x,s,level+1);
  27.         subtree[s]+=subtree[x];
  28.     }
  29.  
  30. }
  31. // DFS End ---------------------------------------------------------------------------
  32.  
  33.  
  34. // LCA Start  --------------------------------------------------------------------------
  35.  
  36. int getlca(int u, int v) {
  37.     if(depth[u] < depth[v]) swap(u,v);
  38.     int diff = depth[u] - depth[v];
  39.     for(int i=0; i<15; i++) if( (diff>>i)&1 ) u = parent[u][i];
  40.     if(u == v) return u;
  41.     for(int i=14; i>=0; i--) if(parent[u][i] != parent[v][i]) {
  42.         u = parent[u][i];
  43.         v = parent[v][i];
  44.     }
  45.     return parent[u][0];
  46. }
  47.  
  48. // LCA End ------------------------------------------------------------------------------
  49.  
  50.  
  51. // SEGTree Begin-------------------------------------------------------------------------
  52. void update(int index,int data,int segindex,int l,int r)
  53. {
  54.     if(l==r){
  55.         baseArray[l]=data;
  56.         seg[segindex]=data;
  57.         return ;
  58.     }
  59.     int mid=(l+r)/2;
  60.     if(index<=mid){
  61.         update(index,data,2*segindex+1,l,mid);
  62.     }else{
  63.         update(index,data,2*segindex+2,mid+1,r);
  64.     }
  65.     seg[segindex]=(seg[2*segindex+1]>seg[2*segindex+2])?seg[2*segindex+1]:seg[2*segindex+2];
  66. }
  67. int query(int index,int l,int r,int ql,int qr)
  68. {
  69.     if(l>=ql && r<=qr)  return seg[index];
  70.     if(l>qr || r<ql)    return 0;
  71.     int mid=(l+r)/2;
  72.     int q1=query(2*index+1,l,mid,ql,qr);
  73.     int q2=query(2*index+2,mid+1,r,ql,qr);
  74.     return (q1>q2)?q1:q2;
  75. }
  76. void buildtree(int l,int r,int index)
  77. {
  78.     if(l==r){
  79.         seg[index]=baseArray[l];
  80.         return;
  81.     }
  82.     int mid=(l+r)/2;
  83.     buildtree(l,mid,2*index+1);
  84.     buildtree(mid+1,r,2*index+2);
  85.     seg[index]=(seg[2*index+1]>seg[2*index+2])?seg[2*index+1]:seg[2*index+2];
  86. }
  87. // SEGTree End--------------------------------------------------------------------------
  88.  
  89.  
  90. // HLD Begin ---------------------------------------------------------------------------
  91. void hld(int s,int p,int _cost)
  92. {
  93.  
  94.     if(chainHead[chainNo]==-1){
  95.         chainHead[chainNo]=s;
  96.     }
  97.  
  98.     posInBase[s]=ptr;       //up wala edge
  99.     baseArray[ptr++]=_cost;
  100.     chainInd[s]=chainNo;
  101.  
  102.     // cout<<s<<" "<<p<<" "<<_cost<<" "<<index<<" "<<posInBase[s]<<" "<<ptr-1<<" "<<baseArray[ptr-1]<<" "<<chainInd[s]<<"\n";   
  103.  
  104.     int ma=0,samechain=-1;
  105.     for(int i=0;i<edges[s].size();i++){
  106.         if(edges[s][i]==p)    continue;
  107.         if(subtree[edges[s][i]]>ma){
  108.             ma=subtree[edges[s][i]];
  109.             samechain=i;
  110.         }
  111.     }
  112.     if(samechain!=-1){
  113.         hld(edges[s][samechain],s,cost[s][samechain]);
  114.     }
  115.     for(int i=0;i<edges[s].size();i++){
  116.         if(edges[s][i]==p || i==samechain)    continue;
  117.         chainNo++;
  118.         hld(edges[s][i],s,cost[s][i]);
  119.     }
  120. }
  121. int query_hld(int u,int v)          //reach v from u
  122. {
  123.     if(u==v)    return 0;
  124.     int chainu,chainv=chainInd[v],ans=0;
  125.     while(true){
  126.         chainu=chainInd[u];
  127.         if(chainu==chainv){
  128.             if(u==v) break;
  129.             int query_result=query(0,0,n-1,posInBase[v]+1,posInBase[u]);
  130.             ans=(ans>=query_result)?ans:query_result;
  131.             return ans;    
  132.         }else{
  133.             int head=chainHead[chainInd[u]];            
  134.             int query_result=query(0,0,n-1,posInBase[head],posInBase[u]);
  135.             ans=(ans>=query_result)?ans:query_result;    
  136.             u=parent[head][0];
  137.         }
  138.     }
  139.     return ans;
  140. }
  141. // HLD End ---------------------------------------------------------------------------
  142.  
  143.  
  144. signed main(){
  145.     fastio
  146.     int t;
  147.     cin>>t;
  148.     while(t--){
  149.         scanf("%d",&n);
  150.  
  151.         ptr=0;chainNo=0;
  152.         for(int i=0;i<=n+10;i++){
  153.             for(int bit=0;bit<=15;bit++){
  154.                 parent[i][bit]=-1;
  155.             }
  156.             chainHead[i]=-1;
  157.             edges[i].clear();
  158.             indices[i].clear();
  159.             cost[i].clear();
  160.         }
  161.  
  162.         for(int i=0;i<n-1;i++){
  163.             int u,v,w;
  164.             scanf("%d %d %d", &u, &v, &w);
  165.             u--,v--;
  166.             edges[u].push_back(v);
  167.             edges[v].push_back(u);
  168.             indices[u].push_back(i);
  169.             indices[v].push_back(i);
  170.             cost[u].push_back(w);
  171.             cost[v].push_back(w);
  172.         }
  173.         dfs(0,-1,0);
  174.         hld(0,-1,0);
  175.         buildtree(0,n-1,0);
  176.         while(true){
  177.             char _type[10];
  178.             scanf("%s",_type);
  179.             if(_type[0]=='D'){
  180.                 break;
  181.             }else if(_type[0]=='Q'){
  182.                 int u,v;
  183.                 scanf("%d %d", &u, &v);
  184.                 u--;v--;
  185.                 if(u==v){
  186.                     printf("0\n");
  187.                     continue;
  188.                 }
  189.                 int lca=getlca(u,v);
  190.                 // cout<<"Coming\n";
  191.                 int q1=query_hld(u,lca),q2=query_hld(v,lca);
  192.                 int ans=(q1>q2)?q1:q2;
  193.                 printf("%d\n",ans);
  194.             }else{
  195.                 int index,data;
  196.                 scanf("%d %d", &index, &data);
  197.                 index--;
  198.                 update(posInBase[bottomvertexofedge[index]],data,0,0,n-1);
  199.             }
  200.         }
  201.     }
  202.     return 0;
  203. }
  204.  
  205. /*
  206. 1
  207. 10
  208. 1 2 3
  209. 2 3 4
  210. 2 4 2
  211. 1 5 9
  212. 5 7 4
  213. 5 8 6
  214. 1 6 8
  215. 6 9 1
  216. 6 10 7
  217. QUERY 3 10
  218. QUERY 7 8
  219. QUERY 7 9
  220. QUERY 5 7
  221. DONE
  222. */
  223.  
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ttWOq8
problem QTREE, based on SPOJ submission 25655080 (CPP), 2020-03-30 00:05:19
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

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!