fork download 
  1. #include <bits/stdc++.h>
  2. #define N int(3e5+10)
  3. #define M 21
  4. #define pb push_back
  5. using namespace std;
  6. int s[N][M],p[N],l[N],n,q,u,v;
  7. vector<int>g[N];
  8. void dfs(int s,int pr){
  9. 	p[s]=pr;
  10. 	if(pr)
  11. 		l[s]=l[pr]+1;
  12. 	for(int i=0;i<g[s].size();i++)
  13. 		if(g[s][i]!=pr)
  14. 			dfs(g[s][i],s);
  15. }
  16. void pre(){
  17. 	for(int i=0;i<=n;i++)
  18. 		for(int j=0;j<M;j++)
  19. 			s[i][j]=0;
  20.  
  21. 	for(int i=1;i<=n;i++)
  22. 		s[i][0]=p[i];
  23.  
  24. 	for(int j=1;(1<<j)<M;j++){
  25. 		for(int i=1;i<=n;i++)
  26. 			s[i][j]=s[s[i][j-1]][j-1];
  27. 	}
  28. }
  29. int f(int a, int d){
  30. 	int logn=0,b=a;
  31. 	while((1<<logn)<=d)
  32. 		logn++;
  33. 	logn--;
  34. 	while(d){
  35. 		if(d&(1<<logn)){
  36. 			d-=(1<<logn);
  37. 			b=s[b][logn];
  38. 		}
  39. 		logn--;
  40. 	}
  41. 	return b;
  42. }
  43. int lca(int u,int v){
  44. 	if(l[u]<l[v])
  45. 		swap(u,v);
  46. 	u=f(u,l[u]-l[v]);
  47. 	if(u==v)
  48. 		return u;
  49. 	int logn=0;
  50. 	while((1<<logn)<=l[v])
  51. 		logn++;
  52. 	logn--;
  53. 	while(logn>=0){
  54. 		if(s[u][logn]&&(s[u][logn]!=s[v][logn])){
  55. 			u=s[u][logn];
  56. 			v=s[v][logn];
  57. 		}
  58. 		logn--;
  59. 	}
  60. 	return p[u];
  61. }
  62. int main() {
  63. 	scanf("%d",&n);
  64. 	for(int i=1;i<n;i++){
  65. 		scanf("%d%d",&u,&v);
  66. 		g[u].pb(v);
  67. 		g[v].pb(u);
  68. 	}
  69. 	dfs(1,0);
  70. 	pre();
  71. 	cin>>q;
  72. 	while(q--){
  73. 		int a,b,c,ans;
  74. 		scanf("%d%d%d",&a,&b,&c);
  75. 		int lc=lca(a,b);
  76. 		int d=l[a]+l[b]-2*l[lc],d1;
  77. 		if(c>=d){
  78. 			ans=b;
  79. 		}else{
  80. 			if(a==lc){
  81. 				ans=f(b,d-c);
  82. 			}else{
  83. 				d1=l[a]-l[lc];
  84. 				if(c>=d1){
  85. 					c-=d1;
  86. 					ans=f(b,l[b]-l[lc]-c);
  87. 				}else{
  88. 					ans=f(a,c);
  89. 				}
  90. 			}
  91. 		}
  92. 		printf("%d\n",ans);
  93. 	}
  94. 	return 0;
  95. }
Success #stdin #stdout 0s 10764KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/A9iHTM
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!