fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define MAX_N 100005
  3. #define eb emplace_back
  4. #define pb push_back
  5. using namespace std;
  6. struct Tree{
  7. 	int l,r,v;
  8. }tree[60*MAX_N];
  9. int n;
  10. int tn;
  11. int par[35][MAX_N],val[MAX_N],dep[MAX_N];
  12. int root[MAX_N];
  13. vector<int> adj[MAX_N];
  14. void update(int idx,int x,int y,int p){
  15. 	tree[y].v=tree[x].v+1;
  16. 	if(idx<0){
  17. 		return ;
  18. 	}
  19. 	if(p>>idx&1){
  20. 		tree[y].l=tree[x].l;
  21. 		tree[y].r=++tn;
  22. 		update(idx-1,tree[x].r,tree[y].r,p);
  23. 	}else{
  24. 		tree[y].r=tree[x].r;
  25. 		tree[y].l=++tn;
  26. 		update(idx-1,tree[x].l,tree[y].l,p);
  27. 	}
  28. }
  29.  
  30. int kQ(int idx,int x,int y,int p,int q,int k){
  31. 	if(idx<0){
  32. 		return 0;
  33. 	}
  34.  
  35. 	int v = tree[tree[x].l].v+tree[tree[y].l].v-tree[tree[p].l].v-tree[tree[q].l].v;
  36.  
  37. 	if(v<k){
  38. 		return (1<<idx)|kQ(idx-1,tree[x].r,tree[y].r,tree[p].r,tree[q].r,k-v);
  39. 	}else{
  40. 		return kQ(idx-1,tree[x].l,tree[y].l,tree[p].l,tree[q].l,k);
  41. 	}
  42. }
  43. void dfs(int x){
  44. 	for(int y:adj[x]){
  45. 		if(root[y])	continue;
  46. 		root[y] = ++tn;
  47. 		update(30,root[x],root[y],val[y]);
  48. 		par[0][y]=x;
  49. 		dep[y]=dep[x]+1;
  50. 		dfs(y);
  51. 	}
  52. }
  53. void make_par(){
  54. 	for(int i=1;i<=30;i++){
  55. 		for(int j=1;j<=n;j++)	par[i][j]=par[i-1][par[i-1][j]];
  56. 	}
  57. }
  58. int lca(int x,int y){
  59. 	if(dep[x]<dep[y]){
  60. 		swap(x,y);
  61. 	}
  62.  
  63. 	for(int i=30;i>=0;i--){
  64. 		if(dep[par[i][x]]>=dep[y]){
  65. 			x=par[i][x];
  66. 		}
  67. 	}
  68.  
  69. 	if(x==y){
  70. 		return x;
  71. 	}
  72.  
  73. 	for(int i=30;i>=0;i--){
  74. 		if(par[i][x]!=par[i][y]){
  75. 			x=par[i][x];
  76. 			y=par[i][y];
  77. 		}
  78. 	}
  79. 	return par[0][x];
  80. }
  81. int main(){
  82. 	int x,y,p,q,m;
  83. 	int i,k;
  84. 	scanf("%d %d",&n,&m);
  85.  
  86. 	for(i=1;i<=n;i++){
  87. 		scanf("%d",&val[i]);
  88. 	}
  89.  
  90. 	for(i=1;i<n;i++){
  91. 		scanf("%d %d",&x,&y);
  92. 		adj[x].eb(y);
  93. 		adj[y].eb(x);
  94. 	}
  95.  
  96. 	root[0] = 0;
  97. 	root[1] = ++tn;
  98.  
  99. 	update(30,0,1,val[1]);
  100.  
  101. 	dep[1]=1;
  102.  
  103. 	dfs(1);
  104. 	make_par();
  105.  
  106. 	while(m--){
  107. 		scanf("%d %d %d",&x,&y,&k);
  108. 		p=lca(x,y);
  109. 		q=par[0][p];
  110. 		printf("%d\n",kQ(30,root[x],root[y],root[p],root[q],k));
  111. 	}
  112. 	return 0;
  113. }
  114.  
Success #stdin #stdout 0s 102720KB
comments (?)
stdin
copy 
3 2
1 2 3
1 2
3 1
2 3 1
1 3 2
stdout
copy 
1
3
https://ideone.com/pApYn1
language:
C++14 (clang 8.0)
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!