fork download
copy 
  1. //Code Author:-code_kika //
  2. //Institution:-IIT(BHU)  //
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. //io
  7. #define sf(x) scanf("%d",&x);
  8. #define sf2(x,y) scanf("%d %d",&x,&y);
  9. #define sf3(x,y,z) scanf("%d %d %d",&x,&y,&z);
  10. #define pf(x) printf("%d",x);
  11. #define pf2(x,y) printf("%d %d",x,y);
  12. #define pf3(x,y,z) printf("%d %d %d",x,y,z);
  13. #define sfl(x) scanf("%lld",&x);
  14. #define sfl2(x,y) scanf("%lld %lld",&x,&y);
  15. #define sfl3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z);
  16. #define pfl(x) printf("%lld",x);
  17. #define pfl2(x,y) printf("%lld %lld",x,y);
  18. #define pfl3(x,y,z) printf("%lld %lld %lld",x,y,z);
  19. #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  20.  
  21. //basic
  22. #define pb push_back
  23. #define ll long long
  24. #define mp make_pair
  25. #define fi first
  26. #define se second
  27. #define mod 1000000007LL
  28.  
  29. //typedefs
  30. #define pii pair<int,int>
  31. #define pll pair<ll,ll>
  32. #define vpii vector<pii>
  33. #define vpll vector<pll>
  34. #define vll vector<ll>
  35. #define vi vector<int>
  36.  
  37. //functions
  38. #define all(c) c.begin(),c.end()
  39. #define fill(c,val) memset(c,val,sizeof(c))
  40.  
  41. //debug
  42. #ifdef TRACE
  43. #define trace(x)                 cerr << #x << ": " << x << endl;
  44. #define trace1(x)                cerr << #x << ": " << x << endl;
  45. #define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  46. #define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  47. #define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  48. #define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  49. #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  50. #else
  51. #define trace(x)
  52. #define trace1(x)
  53. #define trace2(x, y)
  54. #define trace3(x, y, z)
  55. #define trace4(a, b, c, d)
  56. #define trace5(a, b, c, d, e)
  57. #define trace6(a, b, c, d, e, f)
  58. #endif
  59. #define N 100005
  60. int l[N],vis[N],pa[N],dp[N][18];
  61. vi v[N];
  62. void dfs(int node,int lvl){
  63. 	vis[node]=1;
  64. 	l[node]=lvl;
  65. 	for(auto it:v[node]){
  66. 		if(!vis[it]){
  67. 			pa[it]=node;
  68. 			dfs(it,lvl+1);
  69. 		}
  70. 	}
  71. }
  72. //Define pa-parent array, l-level array and dp[N][log(N)]
  73. int lca(int p,int q){
  74.     int i;
  75.     if(l[p]<l[q]){
  76.         int t=p;
  77.         p=q;
  78.         q=t;
  79.     }
  80.  
  81.     int lim;
  82.     for(lim=0;(1<<lim)<=l[p];++lim);
  83.     lim--;
  84.     for(i=lim;i>=0;--i){
  85.         if((l[p]-(1<<i))>=l[q])
  86.             p=dp[p][i];
  87.     }
  88.     if(p==q){
  89.         return p;
  90.     }
  91.     for(i=lim;i>=0;--i){
  92.         if(dp[p][i]!=-1&&dp[p][i]!=dp[q][i]){
  93.             p=dp[p][i];
  94.             q=dp[q][i];
  95.         }
  96.     }
  97.     return pa[p];
  98. }
  99. void pre(int n){
  100.     int i,j;
  101.     for(i=1;i<=n;++i){
  102.         dp[i][0]=pa[i];
  103.     }
  104.     for(i=1;i<=n;i++){
  105.     	for(j=1;j<25;j++){
  106.     		if(dp[i][j-1]){
  107.     			dp[i][j]=dp[dp[i][j-1]][j-1];
  108.     		}
  109.     	}
  110.     }
  111. }
  112. int dis(int p,int q){
  113. 	int lc=lca(p,q);
  114. 	return l[p]-2*l[lc]+l[q];
  115. }
  116. int main(){
  117. 	int a,b,i,root,p,x,y,z,ans,n,q,node;
  118. 	cin>>n>>q;
  119. 	for(i=0;i<n-1;i++){
  120. 		cin>>a>>b;
  121. 		v[a].pb(b);
  122. 		v[b].pb(a);
  123. 	}
  124. 	root=1;
  125. 	pa[root]=0;
  126. 	dfs(1,0);
  127. 	trace(i);
  128. 	pre(n);
  129. 	for(i=0;i<q;i++){
  130. 		cin>>x>>y>>z;
  131. 		p=lca(x,y);
  132. 		p=lca(p,z);
  133. 		int ab=lca(y,z);
  134. 		int bc=lca(z,x);
  135. 		int ca=lca(x,y);
  136. 		ans=1e9;
  137. 		if(dis(p,x)+dis(p,y)+dis(p,z)<ans){
  138. 			ans=dis(p,x)+dis(p,y)+dis(p,z);
  139. 			node=p;
  140. 		}
  141. 		if(dis(x,y)+dis(x,z)<ans){
  142. 			ans=dis(x,y)+dis(x,z);
  143. 			node=x;
  144. 		}
  145. 		if(dis(y,z)+dis(y,x)<ans){
  146. 			ans=dis(y,z)+dis(y,x);
  147. 			node=y;
  148. 		}
  149. 		if(dis(x,z)+dis(z,y)<ans){
  150. 			ans=dis(x,z)+dis(z,y);
  151. 			node=z;
  152. 		}
  153. 		if(dis(ab,x)+dis(ab,y)+dis(ab,z)<ans){
  154. 			ans=dis(ab,x)+dis(ab,y)+dis(ab,z);
  155. 			node=ab;
  156. 		}
  157. 		if(dis(bc,x)+dis(bc,y)+dis(bc,z)<ans){
  158. 			ans=dis(bc,x)+dis(bc,y)+dis(bc,z);
  159. 			node=bc;
  160. 		}
  161. 		if(dis(ca,x)+dis(ca,y)+dis(ca,z)<ans){
  162. 			ans=dis(ca,x)+dis(ca,y)+dis(ca,z);
  163. 			node=ca;
  164. 		}
  165. 		cout<<node<<" "<<ans<<"\n";
  166. 	}
  167.  
  168.  
  169. }
Success #stdin #stdout 0s 26600KB
comments (?)
stdin
copy 
10 3
1 7
4 7
6 2
8 3
9 8
5 8
2 4
3 4
10 7
1 7 8
8 3 10
6 10 3
stdout
copy 
7 4
3 4
4 5
https://ideone.com/r23TAM
language:
C++14 (gcc 8.3)
created:
7 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!