fork(2) download 
  1. /*
  2.     Author:-Sarthak Taneja
  3.     saar2119@gmail.com
  4.     CSE 2nd year,MNNIT Allahabad
  5. */
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11. typedef pair< int,int > ii;
  12. typedef vector< ii > vii;
  13.  
  14. #define sfd(x) scanf("%d",&x)
  15. #define sfs(x) scanf("%s",x)
  16. #define sff(x) scanf("%lf",&x)
  17. #define mod 1000000007
  18. #define MAX 1000000
  19. #define pb push_back
  20. #define mp make_pair
  21. #define fr first 
  22. #define sc second
  23. #define testcases scanf("%d",&t);while(t--)
  24. #define ffor(a,b,c) for(a=b;a<c;a++)
  25. #define rfor(a,b,c) for(a=b;a>=c;a--)
  26.  
  27. int parent[100005]; // for keeping immediate parent of a node
  28. int P[100005][18]; // for keeping 2^j th parent of a node
  29. int maxi[100005][18]; // for maximum length from node to its 2^j th parent
  30. int mini[100005][18]; // for minimum length from node to its 2^j th parent
  31. int level[100005]; // for assigning levels to the node taking 1 as the root always
  32. int root=1;
  33. bool visited[100005]={0}; 
  34. vector< pair<int,int> > graph[100005];
  35.  
  36. void setLevels(int node, int l,int dist)
  37. {
  38. 	level[node]=l;
  39. 	visited[node]=1;
  40. 	if(dist != -1)
  41. 	{
  42. 		maxi[node][0] = mini[node][0] = dist; 
  43. 	}
  44. 	for(int i=0;i<graph[node].size();i++)
  45. 	{
  46. 		if(!visited[graph[node][i].fr])
  47. 		{
  48. 			parent[graph[node][i].fr] = node; // setting parent of a node
  49. 			setLevels(graph[node][i].fr, l+1, graph[node][i].sc);
  50. 		}
  51. 	}
  52. }
  53.  
  54. int lca(int p, int q)
  55. {
  56. 	int tmp,lg,i;
  57.  
  58. 	if(level[p] < level[q]) // if p is above in level then p is swapped with q
  59. 		tmp=p, p=q, q=tmp;
  60.  
  61. 	for(lg=1; (1<<lg) <= level[p]; lg++);
  62. 	lg--;
  63.  
  64. 	for(i=lg;i>=0;i--) //bringing p and q to the same levels 
  65. 	{
  66. 		if(level[p] - (1<<i) >= level[q])
  67. 		{
  68. 			p=P[p][i];
  69. 		}
  70. 	}
  71.  
  72. 	if(p == q)
  73. 		return p;
  74.  
  75. 	for(i=lg;i>=0;i--) // finding lca of p and q by jumping both p and q
  76. 	{
  77. 		if(P[p][i] != -1 && P[p][i] != P[q][i])
  78. 			p=P[p][i], q=P[q][i];
  79. 	}
  80.  
  81. 	return parent[p];
  82. }
  83.  
  84. ii cal(int a,int b) //function to calculate the pair of maximum and minimum from a to its 2^j th parent b using a log(n) loop 
  85. {
  86. 	ii pp;
  87. 	int lg,i;
  88. 	pp.fr=INT_MIN;
  89. 	pp.sc=INT_MAX;
  90.  
  91. 	for(lg=1; (1<<lg) <= level[a]; lg++);
  92. 	lg--;
  93.  
  94. 	for(i=lg;i>=0;i--)
  95. 	{
  96. 		if(level[a] - (1<<i) >= level[b])
  97. 		{
  98. 			pp.fr = max(pp.fr, maxi[a][i]);
  99. 			pp.sc = min(pp.sc, mini[a][i]);
  100. 			a=P[a][i];
  101. 		}
  102. 	}
  103.  
  104. 	return pp;
  105. }
  106.  
  107. int main()
  108. {
  109. 	int i,j,t;
  110. 	int n;
  111. 	int u,v,w;
  112.  
  113. 	{
  114. 		scanf("%d",&n);
  115.  
  116. 		for(i=1;i<=n;i++)
  117. 		{
  118. 			graph[i].clear();
  119. 			visited[i]=0;
  120. 		}
  121.  
  122. 		for(i=0;i<n-1;i++)
  123. 		{
  124. 			scanf("%d%d%d",&u,&v,&w);
  125. 			graph[u].pb(mp(v,w));
  126. 			graph[v].pb(mp(u,w));
  127. 		}
  128. 		root=1;
  129. 		parent[1]=-1;
  130.  
  131. 		for(i=1;i<=n;i++)
  132. 		{
  133. 			for(j=0;j<18;j++)
  134. 			{
  135. 				P[i][j]=-1;
  136. 				maxi[i][j] = INT_MIN;
  137. 				mini[i][j] = INT_MAX;
  138. 			}
  139. 		}
  140.  
  141. 		setLevels(root,0,-1);
  142.  
  143. 		for(i=1;i<=n;i++)
  144. 		{
  145. 			P[i][0]=parent[i];
  146. 		}
  147.  
  148. 		for(j=1;(1<<j)<=n;j++) // dynamic programming loop to assign values of 2^j th parent and maximum and minimum length upto them
  149. 		{
  150. 			for(i=1;i<=n;i++)
  151. 			{
  152. 				if(P[i][j-1] != -1)
  153. 				{
  154. 					P[i][j] = P[P[i][j-1]][j-1];
  155. 					maxi[i][j] = max( maxi[i][j-1], maxi[P[i][j-1]][j-1]);
  156. 					mini[i][j] = min( mini[i][j-1], mini[P[i][j-1]][j-1]);
  157. 				}
  158. 			}
  159. 		}
  160.  
  161. 		int a,b,k;
  162. 		ii pp;
  163. 		ii qq;
  164. 		sfd(k);
  165. 		while(k--)
  166. 		{
  167. 			scanf("%d%d",&a,&b);
  168. 			int lc=lca(a,b); //finding lca of a,b
  169.  
  170. 			if(lc == a)
  171. 			{
  172. 				pp=cal(b,lc);
  173.  
  174. 				printf("%d %d\n", pp.sc, pp.fr);
  175. 			}
  176. 			else if(lc == b)
  177. 			{
  178. 				pp=cal(a,lc);
  179. 				printf("%d %d\n", pp.sc, pp.fr);
  180. 			}
  181. 			else
  182. 			{
  183. 				pp=cal(a,lc);
  184. 				qq=cal(b,lc);
  185. 				pp.fr= max(pp.fr, qq.fr);
  186. 				pp.sc= min(pp.sc, qq.sc);
  187. 				printf("%d %d\n", pp.sc, pp.fr);
  188. 			}
  189. 			//that's it if you have any doubt you can ask it in the comments on http://stackoverflow.com/questions/36083410/how-to-solve-spoj-disquery
  190. 		}
  191. 	}
  192. 	return 0;
  193. }
Success #stdin #stdout 0s 26608KB
comments (?)
stdin 
5 
2 3 100 
4 3 200 
1 5 150 
1 3 50 
3 
2 4 
3 5 
1 2
stdout 
100 200
50 150
50 100
https://ideone.com/fyUapN
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!