fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define mp make_pair 
  5. #define ins insert
  6. #define fi first
  7. #define se second
  8. #define INF   1000000000
  9. #define NINF -1000000000
  10. #define LOGN 22
  11. typedef int ll;
  12. const int N = int(1e5)+10;
  13. vector<pair<int,int>> *graph;
  14.  
  15. bool isBlack[N],isSpecial[N];
  16. int subset_sz[N],chain_group[N];
  17. int data[N],chain_pos[N];
  18.  
  19. typedef struct {
  20.  int a;int b;int wt;
  21. } edge;
  22.  
  23. edge *Edge;
  24.  
  25. typedef struct {
  26.  vector<int> a;int head;int parent=-1;
  27.   int len=0;} chain;
  28.  
  29. chain *Chain;
  30.  
  31. map<pair<int,int>,int> e2i;
  32. ////////////LEAST COMMON ANCESTOR O(LOG(N)) PER QUERY/////////////////////
  33. int level[N];
  34. int DP[LOGN][N];
  35. void dfs0(int u){
  36.     subset_sz[u]=1; 
  37.     int sidx=-1,swt=-1,sit=-1;
  38. 	for(int it=0;it<graph[u].size();++it)
  39.     {int v=graph[u][it].fi;
  40. 		if(v!=DP[0][u])
  41. 		{
  42. 			DP[0][v]=u;
  43. 			level[v]=level[u]+1;
  44. 			dfs0(v);
  45.             if(subset_sz[v]>swt){sidx=v;swt=subset_sz[v];sit=it;}
  46.             subset_sz[u]+=subset_sz[v];
  47. 		}
  48.     }
  49.     if(sidx>-1){
  50.       isSpecial[sidx]=true;
  51.         data[u]=graph[u][sit].se;}
  52. }
  53. void preprocess(int n){
  54.     level[0]=0;
  55. 	DP[0][0]=0;
  56. 	dfs0(0);
  57. 	for(int i=1;i<LOGN;i++)
  58. 		for(int j=0;j<n;j++)
  59. 			DP[i][j] = DP[i-1][DP[i-1][j]];
  60. }
  61. int lca(int a,int b){
  62. 	if(level[a]>level[b])swap(a,b);
  63. 	int d = level[b]-level[a];
  64. 	for(int i=0;i<LOGN;i++)
  65. 		if(d&(1<<i))
  66. 			b=DP[i][b];
  67. 	if(a==b)return a;
  68. 	for(int i=LOGN-1;i>=0;i--)
  69. 		if(DP[i][a]!=DP[i][b])
  70. 			a=DP[i][a],b=DP[i][b];
  71. 	return DP[0][a];
  72. }
  73. //////////////////////////////////////////////////////////////////////////
  74.  
  75. /////////////////HEAVY-LIGHT DECOMPOSITION////////////////////////////////
  76. int max_chain_no=-1;
  77. void hld(int u,int chain_no,int from){   
  78.     Chain[chain_no].a.pb(u); ++Chain[chain_no].len;
  79.     if(Chain[chain_no].len==1) {
  80.      Chain[chain_no].parent=from;
  81.      Chain[chain_no].head=u;   }
  82.      chain_group[u]=chain_no; chain_pos[u]=Chain[chain_no].len-1;
  83.     int sz=graph[u].size();
  84.     for(int i=0;i<graph[u].size();i++){
  85.         int v=graph[u][i].fi;
  86.         if(v!=from) {
  87.           if(isSpecial[v]){hld(v,chain_no,u);}
  88.             else {hld(v,++max_chain_no,u);}
  89.            }
  90.     }
  91. }
  92. ////////////////////CHARACTERIZING OUR DECOMPOSED CHAINS//////////////////////
  93.  
  94. vector<vector<int>> seg_tree;
  95.  
  96. int join(int a,int b){return a>b?a:b;}
  97. void build(){
  98.     for(int it=0;it<=max_chain_no;it++){
  99.      int n= Chain[it].len;   
  100.      vector<int> tree(2*n);
  101.  
  102.      for (int i=0; i<n; i++)    
  103.         tree[n+i] = data[Chain[it].a[i]];
  104.      for (int i = n - 1; i > 0; --i)     
  105.         tree[i] = join(tree[i<<1] ,tree[i<<1 | 1]);
  106.  
  107.      seg_tree.pb(tree);
  108.     }
  109. }
  110. void updateTree(int idx, int val,int chain_no){
  111.     int n= Chain[chain_no].len;
  112.     seg_tree[chain_no][idx+n] = val;  idx= idx+n;
  113.  
  114.     for (int i=idx; i > 1; i >>= 1)
  115.     seg_tree[chain_no][i>>1] = join(seg_tree[chain_no][i],seg_tree[chain_no][i^1]);
  116. }
  117. int queryTree(int l, int r,int chain_no) { 
  118.     int res = NINF;r++;
  119.     int n= Chain[chain_no].len;
  120.     for (l += n, r += n; l < r; l >>= 1, r >>= 1){
  121.         if (l&1) res = join(res,seg_tree[chain_no][l++]);
  122.         if (r&1) res = join(res,seg_tree[chain_no][--r]);
  123.     }
  124.     return res; 
  125. }
  126.  
  127. void update(int i,int wt){
  128.  int a= Edge[i].a, b= Edge[i].b;
  129.  if(DP[0][a]==b){swap(a,b);}
  130.  if(chain_group[a]==chain_group[b]){updateTree(a,wt,chain_group[a]);}
  131.  Edge[i].wt=wt;
  132. }
  133. int query(int a,int b){
  134.  
  135.  int answer=NINF,answer2=NINF;
  136.  int c= lca(a,b);
  137.  int x=a,j,k;
  138.  //printf("[[%d]]",c);
  139.  while(x!=c){
  140.  
  141.   if(chain_group[x]==chain_group[c]){
  142.      answer= max(answer,queryTree(chain_pos[c],chain_pos[DP[0][x]],chain_group[x]));  break; }   
  143.   else{
  144.      if(x!=Chain[chain_group[x]].head)answer= max(answer,queryTree(chain_pos[Chain[chain_group[x]].head],chain_pos[DP[0][x]],chain_group[x]));   
  145.   }
  146.    k=Chain[chain_group[x]].head; x= Chain[chain_group[x]].parent; j=x;
  147.   if(j>k){swap(j,k);}
  148.  // printf("---%d,%d->%d---",j,k,Edge[e2i[mp(j,k)]].wt);
  149.   answer = max(answer,Edge[e2i[mp(j,k)]].wt);
  150.  }
  151.  
  152.  x=b;
  153.  while(x!=c){
  154.  
  155.   if(chain_group[x]==chain_group[c]){
  156.      answer2= max(answer2,queryTree(chain_pos[c],chain_pos[DP[0][x]],chain_group[x]));  break; }   
  157.   else{
  158.      if(x!=Chain[chain_group[x]].head)answer2= max(answer2,queryTree(chain_pos[Chain[chain_group[x]].head],chain_pos[DP[0][x]],chain_group[x]));   
  159.   }
  160.   k=Chain[chain_group[x]].head; x= Chain[chain_group[x]].parent; j=x;
  161.   if(j>k){swap(j,k);}
  162.   //printf("+++%d,%d->%d+++",j,k,Edge[e2i[mp(j,k)]].wt);
  163.  answer2 = max(answer2,Edge[e2i[mp(j,k)]].wt);
  164.  }
  165.  //printf("[%d %d][%d %d]",a,answer,b,answer2);
  166.  return max(answer,answer2);
  167. }
  168.  
  169. //////////////////////////////////////////////////////////////////////////////
  170.  
  171. int main() {
  172.     int t;cin>>t;
  173.     string pt;
  174.     while(getline(cin,pt) and t--){
  175.  
  176.     int n;cin>>n; e2i.clear();
  177.     graph= new vector<pair<int,int>> [n];
  178.     Edge = new edge[n];
  179.  
  180.     for(int i=0;i<n-1;i++)
  181.     {int u,v,w;cin>>u>>v>>w;u--;v--;
  182.      graph[u].pb(mp(v,w));graph[v].pb(mp(u,w)); 
  183.      Edge[i].a=u;Edge[i].b=v; Edge[i].wt= w;    
  184.      if(u>v)swap(u,v); e2i[mp(u,v)]=i;} 
  185.  
  186.     for(int i=0;i<n;i++){isBlack[i]=false;isSpecial[i]=false;data[i]=NINF;}
  187.     max_chain_no=-1;    
  188.     preprocess(n); 
  189.     Chain = new chain[N];
  190.     hld(0,++max_chain_no,-1);
  191.     seg_tree.clear();
  192.     build();
  193.  
  194.     string type;
  195.  
  196.     while(true)
  197.     {
  198.         cin>>type;if(type=="DONE"){break;}
  199.         int q1,q2;cin>>q1>>q2;//scanf("%d%d",&q1,&q2);
  200.         if(type=="CHANGE"){update(q1-1,q2);}
  201.         else if(type=="QUERY"){printf("%d\n",query(q1-1,q2-1));}
  202.         else {break;}
  203.     }
  204.  
  205.     /*    printf("[[[%d]]]",max_chain_no);
  206.         puts("");
  207.      for(int i=0;i<=max_chain_no;i++)
  208.      {
  209.       printf("[%d]",Chain[i].len);for(int j=0;j<Chain[i].a.size();j++){
  210.           printf("{%d %d %d}",Chain[i].a[j]+1,data[Chain[i].a[j]],chain_group[Chain[i].a[j]]);
  211.       }puts("");   
  212.         // printf("%d ",Chain[i].parent);
  213.      } 
  214.       //printf("--[%d]--",queryTree(1,3,0));  
  215.       */
  216.     }
  217.     return 0;
  218. }
  219. /*
  220. 1
  221. 3
  222. 1 2 1
  223. 2 3 2
  224. QUERY 1 2
  225. CHANGE 1 3
  226. QUERY 1 2
  227. DONE
  228.  
  229. */
  230. /*
  231. 1
  232. 23
  233. 1 2 3
  234. 1 3 16 
  235. 1 4 5 
  236. 1 5 20
  237. 2 6 2
  238. 2 8 4
  239. 2 9 5 
  240. 2 10 11
  241. 3 11 18
  242. 4 12 23
  243. 19 23 15
  244. 6 7 1 
  245. 9 13 6
  246. 9 15 8
  247. 10 18 12
  248. 10 19 14
  249. 13 14 7 
  250. 15 16 10
  251. 15 17 9
  252. 18 20 13
  253. 19 21 16
  254. 21 22 17
  255. QUERY 22 3
  256. QUERY 3 22 
  257. QUERY 22 11
  258. QUERY 11 22
  259. QUERY 22 4
  260. QUERY 4 22
  261. QUERY 22 12
  262. QUERY 12 22
  263. QUERY 14 23
  264. QUERY 23 14
  265. DONE
  266. */
  267.  
Success #stdin #stdout 0.01s 19036KB
comments (?)
stdin
copy 
4

23
1 2 3
1 3 16 
1 4 5 
1 5 20
2 6 2
2 8 4
2 9 5 
2 10 11
3 11 18
4 12 23
19 23 15
6 7 1 
9 13 6
9 15 8
10 18 12
10 19 14
13 14 7 
15 16 10
15 17 9
18 20 13
19 21 16
21 22 17
QUERY 22 3
QUERY 3 22 
QUERY 22 11
QUERY 11 22
QUERY 22 4
QUERY 4 22
QUERY 22 12
QUERY 12 22
QUERY 14 23
QUERY 23 14
DONE

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

23
1 2 3
1 3 16 
1 4 5 
1 5 20
2 6 2
2 8 4
2 9 5 
2 10 11
3 11 18
4 12 23
19 23 15
6 7 1 
9 13 6
9 15 8
10 18 12
10 19 14
13 14 7 
15 16 10
15 17 9
18 20 13
19 21 16
21 22 17
QUERY 22 3
QUERY 3 22 
QUERY 22 11
QUERY 11 22
QUERY 22 4
QUERY 4 22
QUERY 22 12
QUERY 12 22
QUERY 14 23
QUERY 23 14
DONE

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
stdout
copy 
17
17
18
18
17
17
23
23
15
15
1
3
17
17
18
18
17
17
23
23
15
15
1
3
https://ideone.com/k3JAze
language:
C++ (gcc 8.3)
created:
6 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!