fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define pi pair<int,int>
  6. #define fi first
  7. #define se second
  8.  
  9. const int N = 10005;
  10.  
  11. // tree rooted at 1
  12. int t,n, cur, par[N], size[N], edge[N], ind[N], ied[N], chainhead[N], tour[N], tree[4*N];
  13. /*  par stores immediate parent
  14.     size stores the size of subtree
  15.     edge stores the weight of ith edge
  16.     ind stores the index of node in euler tour
  17.     ied stores the index of edge in euler tour
  18.     chainhead stores the head of chain of which the node is a part of
  19.     tour stores the weight of edge visited acc to heavy-light decomposition
  20.     tree stores the segment tree for tour
  21. */
  22. vector<pi> adj[N];  //adjacency list for tree
  23. string s;
  24.  
  25. void dfs1(int u, int p){    //finds par of node and size of subtree
  26.     par[u] = p;
  27.     size[u] = 1;
  28.     for(pi i: adj[u]){
  29.         if(i.fi == p)   continue;
  30.         dfs1(i.fi, u);
  31.         size[u] += size[i.fi];
  32.     }
  33. }
  34.  
  35. void dfs2(int u){   //finds the chainhead of nodes according to hld
  36.     int mx = 0, nd = 0, ed;
  37.     if(chainhead[u] == 0)   chainhead[u] = u;
  38.     for(pi i: adj[u]){
  39.         if(i.fi == par[u])  continue;
  40.         if(size[i.fi] > mx){
  41.             mx = size[i.fi];
  42.             nd = i.fi;
  43.             ed = i.se;
  44.         }
  45.     }
  46.     if(nd != 0){
  47.         chainhead[nd] = chainhead[u];
  48.         tour[++cur] = ed;
  49.         ind[nd] = cur;  ied[ed] = cur;
  50.         dfs2(nd);
  51.     }
  52.     for(pi i: adj[u]){
  53.         if(i.fi == par[u] || i.fi == nd)
  54.             continue;
  55.         tour[++cur] = i.se;
  56.         ind[i.fi] = cur;
  57.         ied[i.se] = cur;
  58.         dfs2(i.fi);
  59.     }
  60. }
  61.  
  62. int lca(int u, int v){ 
  63.     while(chainhead[u] != chainhead[v]){
  64.         if(ind[u] > ind[v])
  65.             u = par[chainhead[u]];
  66.         else
  67.             v = par[chainhead[v]];
  68.         if(u == 0)  u = 1;
  69.         if(v == 0)  v = 1;
  70.     }
  71.     return ((ind[u] >= ind[v])?v:u);
  72. }
  73.  
  74. void build(int nd, int s, int e){
  75.     if(s == e){
  76.         tree[nd] = edge[tour[s]];
  77.         return;
  78.     }
  79.     int m = (s + e)>>1;
  80.     build(2*nd, s, m);
  81.     build(2*nd+1, m+1, e);
  82.     tree[nd] = max(tree[2*nd],tree[2*nd+1]);
  83. }
  84.  
  85. void upd(int nd, int s, int e, int i, int v){
  86.     if(s == e){
  87.         tree[nd] = v;
  88.         return;
  89.     }
  90.     int m = (s + e)>>1;
  91.     if(i <= m)
  92.         upd(2*nd, s, m, i, v);
  93.     else
  94.         upd(2*nd+1, m+1, e, i, v);
  95.     tree[nd] = max(tree[2*nd],tree[2*nd+1]);
  96. }
  97.  
  98. int query(int nd, int s, int e, int l, int r){
  99.     if(s > r || e < l || l > r || s > e)
  100.         return 0;
  101.     if(s >= l && e <= r)
  102.         return tree[nd];
  103.     int m = (s + e)>>1;
  104.     return max(query(2*nd, s, m, l, r),query(2*nd+1, m+1, e, l, r));
  105. }
  106.  
  107. void clear(){
  108.     cur = 0;
  109.     memset(chainhead, 0, sizeof chainhead);
  110.     for(int i = 1; i < N; i++)
  111.         adj[i].clear();
  112. }
  113.  
  114. signed main(){
  115.     //freopen("input.txt", "r", stdin);
  116.     scanf("%d",&t);
  117.     while(t--){
  118.         clear();
  119.         scanf("%d",&n); 
  120.         for(int i = 1; i <= n-1; i++){
  121.             int u, v, w;
  122.             scanf("%d %d %d",&u,&v,&w);
  123.             adj[u].pb({v,i});
  124.             adj[v].pb({u,i});
  125.             edge[i] = w;
  126.         }
  127.         dfs1(1,0);
  128.         ind[1] = 0;
  129.         dfs2(1);
  130.         build(1,1,cur);
  131.         while(true){
  132.             cin>>s;
  133.             if(s == "DONE")
  134.                 break;
  135.             else if(s == "CHANGE"){
  136.                 int i,ti;
  137.                 scanf("%d %d",&i,&ti);
  138.                 edge[i] = ti;
  139.                 upd(1,1,cur,ied[i],ti);
  140.             }
  141.             else{
  142.                 int a,b;
  143.                 scanf("%d %d",&a,&b);
  144.                 int u = lca(a,b), ans = 0;
  145.                 while(chainhead[a] != chainhead[u]){
  146.                     ans = max(ans,query(1,1,cur,ind[chainhead[a]],ind[a]));
  147.                     a = par[chainhead[a]];
  148.                 }
  149.                 ans = max(ans,query(1,1,cur,ind[u]+1,ind[a]));
  150.                 a = b;
  151.                 while(chainhead[a] != chainhead[u]){
  152.                     ans = max(ans,query(1,1,cur,ind[chainhead[a]],ind[a]));
  153.                     a = par[chainhead[a]];
  154.                 }
  155.                 ans = max(ans,query(1,1,cur,ind[u]+1,ind[a]));
  156.                 printf("%d\n",ans);
  157.             }
  158.         }
  159.     }
  160.     return 0;
  161. }
Success #stdin #stdout 0s 4284KB
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/EsGUaT
language:
C++ (gcc 8.3)
created:
6 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!