fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int pos;
  4. vector<pair<int,int>> adj[10001];
  5. vector<int> edges[10001];
  6. int level[10001],parent[10001],subtree[10001],dp[10001][14],location[10001],head[10001],arr[10001],segTree[350000];
  7. void dfs(int,int,int);
  8. void hld(int,int,int);
  9. void update(int,int,int,int,int);
  10. void build(int,int,int);
  11. int lca(int,int,int);
  12. int query_up(int,int,int);
  13. int query(int,int,int,int,int);
  14. int main()
  15. {
  16.     ios_base::sync_with_stdio(false);
  17.     cin.tie(NULL);
  18.     string str;
  19.     int tc,i,j,n,a,b,weight;
  20.     cin>>tc;
  21.     while(tc--){
  22.         cin>>n;
  23.         pos=0;
  24.         for(i=1;i<=n-1;i++){
  25.             cin>>a>>b>>weight;
  26.             adj[a].push_back({b,weight});
  27.             adj[b].push_back({a,weight});
  28.             edges[i].push_back(a);
  29.             edges[i].push_back(b);
  30.         }
  31.  
  32.         //cout<<adj[1].size();
  33.         int log=ceil(log2(n));
  34.         level[1]=0;
  35.         dfs(1,1,log);
  36.         head[1]=-1;
  37.         hld(1,0,0);
  38.         build(0,n-1,0);
  39.         int a1,b1;
  40.         while(true){
  41.             cin>>str;
  42.             if(str[0]=='D')
  43.                 break;
  44.             cin>>a1>>b1;
  45.             if(str[0]=='C'){
  46.                 if(level[edges[a1][0]]>level[edges[a1][1]])
  47.                     update(location[edges[a1][0]],0,n-1,0,b1);
  48.                 else
  49.                     update(location[edges[a1][1]],0,n-1,0,b1);
  50.             }
  51.             if(str[0]=='Q'){
  52.                 int l=lca(a1,b1,log);
  53.                 cout<<max(query_up(a1,l,n),query_up(b1,l,n))<<endl;
  54.             }
  55.         }
  56.         for(i=1;i<=n;i++){
  57.             adj[i].clear();
  58.             edges[i].clear();
  59.         }
  60.     }
  61.     return 0;
  62. }
  63. void dfs(int u,int father,int log)
  64. {
  65.     parent[u]=father;
  66.     dp[u][0]=father;
  67.     for(int i=1;i<=log;i++)
  68.         dp[u][i]=dp[dp[u][i-1]][i-1];
  69.     int flag=0,temp;
  70.     for(int i=0;i<adj[u].size();i++){
  71.         temp=adj[u][i].first;
  72.         if(temp!=father){
  73.             level[temp]=level[u]+1;
  74.             dfs(temp,u,log);
  75.             subtree[u]+=subtree[temp]+1;
  76.             flag=1;
  77.         }
  78.     }
  79.     if(flag==0)
  80.         subtree[u]=1;
  81. }
  82. void hld(int u,int p,int value)
  83. {
  84.     if(head[u]==-1)
  85.         head[u]=u;
  86.     else
  87.         head[u]=head[p];
  88.     location[u]=pos;
  89.     arr[pos++]=value;
  90.     int sum=-1;
  91.     int maxsubtree=0,special=-1;
  92.     for(int i=0;i<adj[u].size();i++){
  93.         if(adj[u][i].first!=p){
  94.             if(subtree[adj[u][i].first]>maxsubtree){
  95.                 maxsubtree=subtree[adj[u][i].first];
  96.                 sum=adj[u][i].second;
  97.                 special=adj[u][i].first;
  98.             }
  99.         }
  100.     }
  101.     if(special!=-1){
  102.         hld(special,u,sum);
  103.         for(int i=0;i<adj[u].size();i++){
  104.             if(adj[u][i].first!=special && adj[u][i].first!=p){
  105.                 head[adj[u][i].first]=-1;
  106.                 hld(adj[u][i].first,u,adj[u][i].second);
  107.             }
  108.         }
  109.     }
  110. }
  111. void update(int u,int low,int high,int pos,int tochange)
  112. {
  113.     if(u<low || u>high)
  114.         return;
  115.     if(low==high){
  116.         segTree[pos]=tochange;
  117.         return;
  118.     }
  119.     int mid=(low+high)/2;
  120.     update(u,low,mid,2*pos+1,tochange);
  121.     update(u,mid+1,high,2*pos+2,tochange);
  122.     segTree[pos]=(segTree[2*pos+1]>segTree[2*pos+2])?segTree[2*pos+1]:segTree[2*pos+2];
  123. }
  124. void build(int low,int high,int pos)
  125. {
  126.     if(low==high){
  127.         segTree[pos]=arr[low];
  128.         return;
  129.     }
  130.     int mid=(low+high)/2;
  131.     build(low,mid,2*pos+1);
  132.     build(mid+1,high,2*pos+2);
  133.     segTree[pos]=(segTree[2*pos+1]>segTree[2*pos+2])?segTree[2*pos+1]:segTree[2*pos+2];
  134. }
  135. int lca(int a,int b,int log)
  136. {
  137.     if(level[a]<level[b])
  138.         swap(a,b);
  139.     for(int i=log;i>=0;i--){
  140.         if(level[a]-(int)(pow(2,i)+0.5)>=level[b])
  141.             a=dp[a][i];
  142.     }
  143.     if(a==b)
  144.         return a;
  145.     for(int i=log;i>=0;i--){
  146.         if(dp[a][i]!=dp[b][i]){
  147.             a=dp[a][i];
  148.             b=dp[b][i];
  149.         }
  150.     }
  151.     return dp[a][0];
  152. }
  153. int query_up(int a,int l,int n)
  154. {
  155.     int maximum=0;
  156.     while(true){
  157.     if(a==l)
  158.         return maximum;
  159.     if(head[a]==head[l])
  160.         return maximum=max(maximum,query(location[head[a]],location[a],0,n-1,0));
  161.     else if(head[a]!=head[l]){
  162.         maximum=max(maximum,query(location[head[a]],location[a],0,n-1,0));
  163.         a=parent[head[a]];
  164.     }
  165.     }
  166. }
  167. int query(int qlow,int qhigh,int low,int high,int pos)
  168. {
  169.     if(qhigh<low || qlow>high)
  170.         return -1;
  171.     if(low>=qlow && high<=qhigh)
  172.         return segTree[pos];
  173.     int mid=(low+high)/2;
  174.     return max(query(qlow,qhigh,low,mid,2*pos+1),query(qlow,qhigh,mid+1,high,2*pos+2));
  175. }
  176.  
Success #stdin #stdout 0s 4412KB
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/0VzhjU
language:
C++14 (gcc 8.3)
created:
3 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!