fork download
copy 
  1. //agrawal117
  2. //chahatagrawal117
  3. #include<bits/stdc++.h>
  4. #define endl '\n'
  5. #define mod 1000000007
  6. typedef long long int ll;
  7. using namespace std;
  8. #define MAX 10005
  9. #define MAXLOG 14
  10. int chainId[MAX]; // chainId on ith node
  11. int position[MAX]; // position in base array of  ith node
  12. int chainHead[MAX];  // which head node is there at ith chain
  13.  
  14. int chain=1;
  15. int pos=1;
  16.  
  17. int subtree[MAX];
  18. int level[MAX];
  19. int parent[MAX][MAXLOG];
  20. int logs[MAX];
  21.  
  22. vector<pair<ll,ll>> v[MAX];
  23.  
  24. ll tree[MAX<<2];
  25. ll arr[MAX];    // denotes weight array ( //base array )
  26. ll n;
  27. pair<int,int> edges[MAX];
  28. void clear()
  29. {
  30.     chain=1;
  31.     pos=1;
  32.     for(int i=1;i<=n;i++) for(int j=0;j<MAXLOG;j++) parent[i][j]=-1;
  33.     for(int i=1;i<=n;i++) v[i].clear();
  34. }
  35. void log_power()
  36. {
  37.     logs[1]=0;
  38.     for(int i=2;i<MAX;i++) logs[i]=logs[i/2]+1;
  39. }
  40.  
  41.  
  42.  
  43. ll combine(ll a,ll b)					// 1 based indexing remember;
  44. {
  45. 	if(a>=b) return a;
  46. 	return b;
  47. }
  48.  
  49. void build(ll start,ll end,ll node)
  50. {
  51. 	if(start==end){
  52. 		tree[node]=arr[start];
  53. 		return;
  54. 	}
  55. 	ll mid=(start+end)>>1;
  56. 	build(start,mid,2*node);
  57. 	build(mid+1,end,(2*node)+1);
  58. 	tree[node]=combine(tree[2*node],tree[(2*node)+1]);
  59. }
  60.  
  61. ll query(ll start,ll end,ll node,ll l,ll r)
  62. {
  63. 	if(start>r || l>end) {				//no overlap case  return that value which does not affect the ans 
  64. 		return INT_MIN;							// as in case of sum we can return 0;
  65. 	}
  66. 	else if(l<=start && r>=end) {
  67. 		return tree[node];           // case of fully overlap
  68. 	}
  69. 	else{
  70. 		ll mid=(start+end)>>1;								//partial overlap so call both children
  71. 		ll child1=query(start,mid,2*node,l,r);
  72. 		ll child2=query(mid+1,end,(2*node)+1,l,r);
  73. 		return combine(child1,child2);
  74. 	}
  75. }
  76.  
  77. void update(ll start,ll end,ll node,ll idx,ll value)
  78. {
  79. 	 if(start==end){
  80. 		tree[node]=value;
  81. 		arr[start]=value;
  82. 		return;
  83. 	}
  84. 	ll mid=(start+end)>>1;	
  85. 	if(start<=idx && idx<=mid){
  86. 	 update(start,mid,2*node,idx,value);
  87. 	}
  88. 	 else{
  89. 		update(mid+1,end,(2*node)+1,idx,value);
  90. 	 }
  91. 	tree[node]=combine(tree[2*node],tree[(2*node)+1]);
  92. }
  93.  
  94.  
  95. ll query_up(int a, int b) // b must be the ancestor of a
  96. {
  97.  
  98.     ll ans=0;
  99.     while(chainId[a]!=chainId[b]){
  100.         int ch=chainId[a];
  101.         int head=chainHead[ch];
  102.         ll val=query(1,n,1,position[head],position[a]);
  103.         ans=combine(ans,val);
  104.         a=parent[head][0];
  105.     }
  106.     if(a==b) return ans;
  107.     // now in same chain left limit is position[b]+1 as at this position. weight of b and its heavy child is there
  108.     ll val=query(1,n,1,position[b]+1, position[a]);
  109.     ans=combine(ans,val);
  110.     return ans;
  111. }
  112.  
  113. void hld(int node, int par,ll weight)
  114. {
  115.     position[node]=pos;
  116.     arr[pos]=weight;
  117.     chainId[node]=chain;
  118.     pos++;
  119.     int hnode=-1; int hsize=0; int hweight=-1;   // heavynode // heavy_subtree_size // heavy weight
  120.     for(auto i: v[node]){
  121.         if(i.first==par) continue;
  122.         if(subtree[i.first]>hsize) {
  123.             hsize=subtree[i.first];
  124.             hnode=i.first;
  125.             hweight=i.second;
  126.         }
  127.     }
  128.     if(hnode!=-1){
  129.         hld(hnode,node,hweight);
  130.     }
  131.  
  132.     for(auto i: v[node])         // for rest of the nodes
  133.     {
  134.         if(i.first==par || i.first ==hnode) continue;
  135.         chain++;
  136.         chainHead[chain]=i.first;
  137.         hld(i.first,node,i.second);
  138.     }
  139.  
  140. }
  141. void dfs(int node , int par)
  142. {
  143.     subtree[node]=1;
  144.     parent[node][0]=par;
  145.     for(int i=1;i<MAXLOG;i++){
  146.         if(parent[node][i]!=-1) parent[node][i]=parent[parent[node][i-1]][i-1];
  147.     }
  148.     for(auto i: v[node])
  149.     {
  150.         if(i.first==par) continue;
  151.         level[i.first]=level[node]+1;
  152.         dfs(i.first,node);
  153.         subtree[node]+=subtree[i.first];
  154.     }
  155. }
  156. int LCA(int a, int b)
  157. {
  158.     if(level[a]<level[b]) swap(a,b);
  159.     ll dist=level[a]-level[b];
  160.     while(dist>0)
  161.     {
  162.         a=parent[a][logs[dist]];
  163.         dist=(dist-(1LL<<logs[dist]));
  164.     }
  165.     if(a==b) return a;
  166.     for(int i=MAXLOG-1;i>=0;i--){
  167.         if(parent[a][i]!=-1 && parent[b][i]!=-1 && parent[a][i]!=parent[b][i]) a=parent[a][i], b=parent[b][i];
  168.     }
  169.     return parent[a][0];
  170. }
  171.  
  172. int main()
  173. {
  174.     // ios_base::sync_with_stdio(0);
  175.     // cin.tie(0);
  176.     // cout.tie(0);
  177.     int t; scanf("%d", &t);
  178.     log_power();
  179.     while(t--)
  180.     {
  181.         scanf("%d", &n);
  182.         for(int i=1;i<=n-1;i++){
  183.             ll a,b,c; scanf("%lld %lld %lld", &a, &b, &c);
  184.             v[a].push_back({b,c});
  185.             v[b].push_back({a,c});
  186.             edges[i]={a,b};
  187.         }
  188.         dfs(1,-1);
  189.  
  190.         chainHead[1]=1;
  191.         hld(1,-1,0);
  192.  
  193.         build(1,n,1);
  194.  
  195.         ll a,b,c;
  196.         while(1)
  197.         {
  198.             char s[10];
  199. 			scanf("%s", s);
  200.             if(s[0]=='D') break;
  201.             if(s[0]=='Q') {
  202.                 scanf("%lld %lld", &a, &b);
  203.                 int lca=LCA(a,b);
  204.                 ll ans=query_up(a,lca);
  205.                 ll val=query_up(b,lca);
  206.                 ans=combine(ans,val);
  207.                 printf("%lld\n", ans);
  208.             }
  209.             else{
  210.                scanf("%lld %lld", &a, &c);
  211.                 int x=edges[a].first; int y=edges[a].second;
  212.                 if(level[x]<level[y]) swap(x,y); 
  213.                 update(1,n,1,position[x],c);
  214.             }
  215.         }
  216.         clear();
  217.  
  218.     }
  219.  
  220.     return 0;
  221. }
Success #stdin #stdout 0s 4400KB
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/dysO31
language:
C++14 (gcc 8.3)
created:
4 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!