fork(1) download
copy 
  1. /*
  2.     Author:-Sarthak Taneja
  3.     CSE 2nd year,MNNIT Allahabad
  4. */
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. #define root 0
  10. #define N 10005
  11. #define LN 14
  12.  
  13. vector<int> adj[N], costs[N], indexx[N];
  14. int baseArray[N], ptr;
  15. int chainNo, chainInd[N], chainHead[N], posInBase[N];
  16. int level[N], P[N][LN], otherEnd[N], subsize[N];
  17. int st[N*6], qt[N*6];
  18.  
  19. void make_tree(int curr, int start, int end)
  20. {
  21. 	if(start == end-1)
  22. 	{
  23. 		st[curr] = baseArray[start];
  24. 		return;
  25. 	}
  26.  
  27. 	int child1=(curr<<1);
  28. 	int child2=child1 | 1;
  29. 	int mid= (start + end)>>1;
  30.  
  31. 	make_tree(child1, start, mid);
  32. 	make_tree(child2, mid, end);
  33. 	st[curr] = max(st[child1], st[child2]);
  34. }
  35.  
  36. void update_tree(int curr, int start, int end, int x, int val)
  37. {
  38. 	if(start > x || end <= x) 
  39. 		return;
  40. 	if(start == x && start == end-1)
  41. 	{
  42. 		st[curr] = val;
  43. 		return;
  44. 	}
  45. 	int c1 = (curr<<1), c2 = c1 | 1, m = (start+end)>>1;
  46. 	update_tree(c1, start, m, x, val);
  47. 	update_tree(c2, m, end, x, val);
  48. 	st[curr] = max(st[c1], st[c2]);
  49. }
  50.  
  51. void query_tree(int curr, int start, int end, int S, int E)
  52. {
  53. 	if(start >= E || end <= S)
  54. 	{
  55. 		qt[curr]=-1;
  56. 		return;
  57. 	}
  58. 	else if(start >= S && end <= E)
  59. 	{
  60. 		qt[curr] = st[curr];
  61. 		return;
  62. 	}
  63.  
  64. 	int child1= (curr<<1);
  65. 	int child2= child1 | 1;
  66. 	int mid= (start + end)>>1;
  67. 	query_tree(child1, start, mid, S, E);
  68. 	query_tree(child2, mid, end, S, E);
  69. 	qt[curr] = max(qt[child1], qt[child2]);
  70. }
  71.  
  72.  
  73. int query_up(int u,int v)
  74. {
  75. 	if(u == v)
  76. 		return 0;
  77.  
  78. 	int uchain;
  79. 	int vchain = chainInd[v];
  80. 	int ans=-1;
  81.  
  82. 	while(1)
  83. 	{
  84. 		uchain = chainInd[u];
  85. 		if(uchain == vchain)
  86. 		{
  87. 			if(u == v)
  88. 				break;
  89. 			query_tree(1, 0, ptr, posInBase[v]+1, posInBase[u]+1);
  90. 			ans = max(ans, qt[1]);
  91. 			break;
  92. 		}
  93.  
  94. 		query_tree(1, 0, ptr, posInBase[chainHead[uchain]], posInBase[u]+1);
  95. 		ans = max(ans, qt[1]);
  96. 		u=P[chainHead[uchain]][0];	
  97. 	}
  98.  
  99. 	return ans;
  100. }
  101.  
  102. int lca(int p, int q)
  103. {
  104. 	int tmp,lg,i;
  105.  
  106. 	if(level[p] < level[q])
  107. 		tmp=p, p=q, q=tmp;
  108.  
  109. 	for(lg=1; (1<<lg) <= level[p]; lg++);
  110. 	lg--;
  111.  
  112. 	for(i=lg;i>=0;i--)
  113. 	{
  114. 		if(level[p] - (1<<i) >= level[q])
  115. 		{
  116. 			p=P[p][i];
  117. 		}
  118. 	}
  119.  
  120. 	if(p == q)
  121. 		return p;
  122.  
  123. 	for(i=lg;i>=0;i--)
  124. 	{
  125. 		if(P[p][i] != -1 && P[p][i] != P[q][i])
  126. 			p=P[p][i], q=P[q][i];
  127. 	}
  128.  
  129. 	return P[p][0];
  130. }
  131.  
  132. void query(int u,int v)
  133. {
  134. 	int lc=lca(u,v);
  135. 	int ans = max( query_up(u, lc), query_up(v, lc));
  136. 	printf("%d\n",ans);
  137. }
  138.  
  139. void change(int i, int val) 
  140. {
  141. 	int u = otherEnd[i];
  142. 	update_tree(1, 0, ptr, posInBase[u], val);
  143. }
  144.  
  145. void HLD(int curr, int cost, int prev)
  146. {
  147. 	int i;
  148. 	if(chainHead[chainNo] == -1)
  149. 	{
  150. 		chainHead[chainNo] == curr;
  151. 	}
  152.  
  153. 	chainInd[curr]=chainNo;
  154. 	posInBase[curr]=ptr;
  155. 	baseArray[ptr++]=cost;
  156.  
  157. 	int sc=-1,ncost;
  158.  
  159. 	for(i=0;i<adj[curr].size();i++)
  160. 	{
  161. 		if(adj[curr][i] != prev)
  162. 		{
  163. 			if(sc == -1 || subsize[sc] < subsize[adj[curr][i]])
  164. 			{
  165. 				sc=adj[curr][i];
  166. 				ncost= costs[curr][i];
  167. 			}
  168. 		}
  169. 	}
  170.  
  171. 	if(sc != -1)
  172. 	{
  173. 		HLD(sc, ncost, curr);
  174. 	}
  175.  
  176. 	for(i=0;i<adj[curr].size();i++)
  177. 	{
  178. 		if(adj[curr][i] != sc && adj[curr][i] != prev)
  179. 		{
  180. 			chainNo++;
  181. 			HLD(adj[curr][i], costs[curr][i], curr);
  182. 		}
  183. 	}
  184.  
  185. }
  186.  
  187. void setLevels(int curr, int prev, int l=0)
  188. {
  189. 	P[curr][0]=prev;
  190. 	level[curr]=l;
  191. 	subsize[curr]=1;
  192. 	for(int i=0;i<adj[curr].size();i++)
  193. 	{
  194. 		if(adj[curr][i] != prev)
  195. 		{
  196. 			otherEnd[indexx[curr][i]] = adj[curr][i];
  197. 			setLevels(adj[curr][i], curr, l + 1);
  198. 			subsize[curr] += subsize[adj[curr][i]]; 
  199. 		}
  200. 	}
  201. }
  202.  
  203. int main()
  204. {
  205. 	int i,j,t;
  206. 	int n;
  207. 	char s[20];
  208. 	int u,v,w;
  209.  
  210. 	scanf("%d",&t);
  211. 	while(t--)
  212. 	{
  213. 		scanf("%d",&n);
  214. 		ptr=0;
  215.  
  216. 		for(i=0;i<n;i++)
  217. 		{
  218. 			adj[i].clear();
  219. 			costs[i].clear();
  220. 			indexx[i].clear();
  221. 			chainHead[i]=-1;
  222. 			for(j=0;j<LN;j++)
  223. 				P[i][j]=-1;
  224. 		}
  225.  
  226. 		for(i=0;i<n-1;i++)
  227. 		{
  228. 			scanf("%d%d%d",&u,&v,&w);
  229. 			u--;
  230. 			v--;
  231. 			adj[u].push_back(v);
  232. 			adj[v].push_back(u);
  233. 			costs[u].push_back(w);
  234. 			costs[v].push_back(w);
  235. 			indexx[u].push_back(i);
  236. 			indexx[v].push_back(i);
  237. 		}
  238.  
  239. 		chainNo=0;
  240. 		setLevels(root,-1);
  241. 		HLD(root, -1, -1);
  242. 		make_tree(1, 0, ptr);
  243.  
  244. 		for(j=1;j<LN;j++)	
  245. 		{
  246. 			for(i=0;i<n;i++)
  247. 			{
  248. 				if(P[i][j-1] != -1)
  249. 				P[i][j] = P[P[i][j-1]][j-1];
  250. 			}
  251. 		}
  252.  
  253. 		while(1)
  254. 		{
  255. 			scanf("%s",s);
  256.  
  257. 			if(s[0] == 'D')
  258. 				break;
  259.  
  260. 			scanf("%d%d",&u,&v);
  261. 			if(s[0] == 'Q')
  262. 				query(u-1,v-1);
  263. 			else
  264. 				change(u-1,v);
  265. 		}
  266. 	}
  267. 	return 0;	
  268. }
Success #stdin #stdout 0s 5060KB
comments (?)
stdin
copy 
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
stdout
copy 
1
3
https://ideone.com/CTgDs3
language:
C++ (gcc 8.3)
created:
8 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!