fork(2) download
copy 
  1. #include<cmath>
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<vector>
  5. #include<algorithm>
  6. using namespace std;
  7. #define MX 10004
  8. #define lft n<<1
  9. #define ryt (n<<1)+1
  10. #define mid (int)((b+e)>>1)
  11. #define lson lft,b,mid
  12. #define rson ryt,mid+1,e
  13. #define N tree[n]
  14. #define L tree[lft]
  15. #define R tree[ryt]
  16. ////////////////////////////////////////
  17. ////////////////////////////////////////
  18.  
  19.  
  20. vector<int>g[MX],cost[MX],index[MX];
  21. int lvl[MX],p[32][MX]; //for Sparse Table
  22. int visited[MX],uv[MX]; // for dfs
  23. int hld[MX],hldpos[MX],chainid[MX],head[MX],sub[MX],chain,pos; // for HLD
  24. int tree[4*MX]; //segment tree
  25.  
  26. //OK
  27. void dfs(int u)
  28. {
  29.     visited[u] = 1;
  30.     int i,v,sz=g[u].size();
  31.     for(i=0;i<sz;i++){
  32.         v = g[u][i];
  33.         if(!visited[v]){
  34.             sub[v]++;
  35.             uv[index[u][i]] = v;
  36.             p[0][v] = u;
  37.             lvl[v] = lvl[u] + 1;
  38.             dfs(v);
  39.             sub[u] += sub[v];
  40.         }
  41.     }
  42. }
  43.  
  44.  
  45. //OK
  46. void SparseTable(int n)
  47. {
  48.     int i,j,lg=log2(n);
  49.     for(i=1;i<=lg;i++){
  50.         for(j=1;j<=n;j++){
  51.             int pp = p[i-1][j];
  52.             if(pp==-1) p[i][j] = -1;
  53.             else p[i][j] = p[i-1][pp];
  54.         }
  55.     }
  56. }
  57.  
  58. //OK
  59. int lca(int n, int u, int v)
  60. {
  61.     if(lvl[u]<lvl[v]) swap(u,v);
  62.     int i,j,lg=log2(n);
  63.     for(i=lg;i>=0;i--){
  64.         int uu=p[i][u];
  65.         if(uu!=-1 && lvl[u]-(1<<i)>=lvl[v]) u=uu;
  66.     }
  67.     if(u==v) return u;
  68.     for(i=lg;i>=0;i--){
  69.         int uu = p[i][u];
  70.         int vv = p[i][v];
  71.         if(uu!=-1 && vv!=-1 && uu!=vv) u=uu,v=vv;
  72.     }
  73.     return p[0][u];
  74. }
  75.  
  76. //OK
  77. void HLD(int u, int c, int pre)
  78. {
  79.     if(!head[chain]) head[chain] = u;
  80.     chainid[u] = chain;
  81.     hldpos[u] = pos;
  82.     hld[pos] = c;
  83.     pos++;
  84.     int heavy = 0, hsub=0;
  85.     int i,v,hcost,sz=g[u].size();
  86.     for(i=0;i<sz;i++){
  87.         v = g[u][i];
  88.         if(v!=pre)
  89.         if(sub[v]>hsub){
  90.             heavy = v;
  91.             hsub = sub[v];
  92.             hcost = cost[u][i];
  93.         }
  94.     }
  95.     if(heavy) HLD(heavy,hcost,u);
  96.     for(i=0;i<sz;i++){
  97.         v = g[u][i];
  98.         if(v!=pre)
  99.         if(v!=heavy){
  100.             chain++;
  101.             HLD(v,cost[u][i],u);
  102.         }
  103.     }
  104. }
  105.  
  106. //OK
  107. void Build(int n, int b, int e)
  108. {
  109.     if(b==e){
  110.         N = hld[b];
  111.         return;
  112.     }
  113.     Build(lson);
  114.     Build(rson);
  115.     N = max(L,R);
  116. }
  117.  
  118. //OK
  119. void Update(int n, int b, int e, int x, int v)
  120. {
  121.     if(b>x || e<x) return;
  122.     if(b==e && b==x){
  123.         N = v;
  124.         return;
  125.     }
  126.     Update(lson,x,v);
  127.     Update(rson,x,v);
  128.     N = max(L,R);
  129. }
  130.  
  131. //OK
  132. int Find(int n, int b, int e, int x, int y)
  133. {
  134.     if(b>y || e<x) return 0;
  135.     if(b>=x && e<=y) return N;
  136.     int f1 = Find(lson,x,y);
  137.     int f2 = Find(rson,x,y);
  138.     return max(f1,f2);
  139. }
  140.  
  141. //OK
  142. int query(int n, int u, int v)
  143. {
  144.     if(u==v) return 0;
  145.     int uchain,vchain,i,r=0;
  146.     vchain = chainid[v];
  147.     while(1){
  148.         if(u==v) return r;
  149.         uchain = chainid[u];
  150.         int up = hldpos[u];
  151.         int vp = hldpos[v];
  152.         int hp = hldpos[head[uchain]];
  153.         if(uchain==vchain){
  154.             if(up>vp) swap(up,vp);
  155.             r = max(r,Find(1,1,n,up,vp));
  156.             return r;
  157.         }
  158.         r = max(r,Find(1,1,n,hp,up));
  159.         u = head[uchain];
  160.         u = p[0][u];
  161.     }
  162. }
  163.  
  164. //OK
  165. int main()
  166. {
  167.     int i,j,n,test,u,v,w;
  168.     scanf("%d",&test);
  169.     while(test--){
  170.         scanf("%d",&n);
  171.         for(i=0;i<=n;i++){
  172.             g[i].clear();
  173.             cost[i].clear();
  174.             index[i].clear();
  175.             visited[i]=0;
  176.             sub[i]=0;
  177.             head[i]=0;
  178.         }
  179.         for(i=1;i<n;i++){
  180.             scanf("%d%d%d",&u,&v,&w);
  181.             g[u].push_back(v);
  182.             g[v].push_back(u);
  183.             cost[u].push_back(w);
  184.             cost[v].push_back(w);
  185.             index[u].push_back(i);
  186.             index[v].push_back(i);
  187.         }
  188.         sub[1]=1;
  189.         lvl[1] = 0;
  190.         p[0][1] = -1;
  191.         dfs(1);
  192.         SparseTable(n);
  193.  
  194.         chain=1;
  195.         pos=1;
  196.         HLD(1,0,0);
  197.         Build(1,1,n);
  198.         //for(i=1;i<pos;i++) cout<<hld[i]<<" "; cout<<endl;
  199.         //for(i=1;i<=3*n;i++) cout<<tree[i]<<" "; cout<<endl;
  200.         char s[100];
  201.         while(1){
  202.             scanf("%s",s);
  203.             if(s[0]=='D') break;
  204.             scanf("%d%d",&u,&v);
  205.             if(s[0]=='C'){
  206.                 u = uv[u];
  207.                 Update(1,1,n,hldpos[u],v);
  208.             }
  209.             if(s[0]=='Q'){
  210.                 int _lca = lca(n,u,v);
  211.                 int x = query(n,u,_lca);
  212.                 int y = query(n,v,_lca);
  213.                 printf("%d\n",max(x,y));
  214.             }
  215.         }
  216.     }
  217.     return 0;
  218. }
  219.  
Success #stdin #stdout 0s 5544KB
comments (?)
stdin
copy 
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
stdout
copy 
1
3
https://ideone.com/AZJpmJ
language:
C++14 (gcc 8.3)
created:
8 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!