fork download
copy 
  1. import java.io.*;
  2. import java.math.*;
  3. import java.util.*;
  4. /* 
  5. 																yash jobanputra
  6. 																	DA-IICT
  7. */
  8. class mstkp {
  9. 	private static InputStream stream;
  10. 	private static byte[] buf = new byte[1024];
  11. 	private static int curChar;
  12. 	private static int numChars;
  13. 	private static SpaceCharFilter filter;
  14. 	private static PrintWriter pw;
  15. 	private static long mod = 1000000000 + 7;
  16. 	private static long mod1 = 1000000000 + 9;
  17. 	private static int MAX=1000001;
  18. 	private static int block;
  19. 	private static int count;
  20. 	private static boolean[] vis;
  21. 	private static Stack<Integer> st;
  22. 	private static int times=0;
  23. 	public static int cc;
  24. 	public static int pos;
  25. 	private static void soln(){
  26. 			int t=ni();
  27. 			for(int c=0;c<t;c++)
  28. 			{
  29. 				int n=ni();
  30. 				ArrayList<Pair>[] tree=new ArrayList[n+1];
  31. 				int[][] ecost=new int[n+1][n+1];
  32. 				for(int i=0;i<=n;i++)
  33. 				{
  34. 					tree[i]=new ArrayList<>();
  35. 				}
  36. 				for(int i=1;i<n;i++)
  37. 				{
  38. 					int a=ni();int b=ni();int cost=ni();
  39. 					tree[a].add(new Pair(b,i));
  40. 					tree[b].add(new Pair(a,i));
  41. 					ecost[a][b]=cost;
  42. 					ecost[b][a]=cost;
  43. 				}
  44. 				hld.initial(n);
  45. 				hld.dfs(1, 1, tree);
  46. 				hld.ilca(n);
  47. 				hld.Hld(1, 0, -1, tree, ecost);
  48. 				hld.build(1, 1, pos);
  49. 				while(true)
  50. 				{
  51. 					String[] s=nli().split(" ");
  52. 					if(s[0].contentEquals("DONE"))
  53. 						break;
  54. 					else if(s[0].contentEquals("QUERY"))
  55. 						pw.println(hld.querypath(Integer.parseInt(s[1]), Integer.parseInt(s[2])));
  56. 					else
  57. 						hld.update(Integer.parseInt(s[1]), Integer.parseInt(s[2]));
  58. 				}
  59. 			}
  60. 		}
  61. 	public static class hld
  62. 	{
  63. 		static int[][] p;static int[] dp;static int[] subsize;static int[] endnode;static int chainno;static int[] chainhead,chainind,arrpos,costarr,segtree;
  64. 		public static void initial(int n)
  65. 		{
  66. 			p=new int[n+1][22];
  67. 			dp=new int[n+1];
  68. 			subsize=new int[n+1];
  69. 			endnode=new int[n];
  70. 			chainhead=new int[n+1];
  71. 			chainind=new int[n+1];
  72. 			arrpos=new int[n+1];
  73. 			costarr=new int[n];
  74. 			segtree=new int[n*4];
  75. 			chainno=1;
  76. 			pos=-1;
  77. 			Arrays.fill(chainhead, -1);
  78. 		}
  79. 		public static void ilca(int n)
  80. 		{
  81. 			for(int i=1;i<=n;i++)
  82. 			{
  83. 				for(int j=1;j<22;j++)
  84. 					p[i][j]=-1;
  85. 			}
  86. 			for(int j=1;1<<j<=n;j++)
  87. 			{
  88. 				for(int i=1;i<=n;i++)
  89. 				{
  90. 					if(p[i][j-1]!=-1)
  91. 						p[i][j]=p[p[i][j-1]][j-1];
  92. 				}
  93. 			}
  94. 		}
  95. 		public static void dfs(int node,int par,ArrayList<Pair>[] tree)
  96. 		{
  97. 			if(par==0)	dp[node]=0;
  98. 			subsize[node]=1;
  99. 			p[node][0]=par;
  100. 			for(int i=0;i<tree[node].size();i++)
  101. 			{
  102. 				int next=tree[node].get(i).v;
  103. 				int ind=tree[node].get(i).i;
  104. 				if(next!=par)
  105. 				{
  106. 					endnode[ind]=next;
  107. 					dfs(next,node,tree);
  108. 					subsize[node]+=subsize[next];
  109. 				}
  110. 			}
  111. 		}
  112. 		public static int lca(int u,int v)
  113. 		{
  114. 			if(dp[u]<dp[v])
  115. 			{
  116. 				int temp=u;
  117. 				u=v;
  118. 				v=temp;
  119. 			}
  120. 			int log;
  121. 			for (log = 1; 1 << log <= dp[u]; log++);
  122. 		      log--;
  123. 		    for(int i=log;i>=0;i--)
  124. 		    {
  125. 		    	if(dp[u]-(1<<i)>=dp[v])
  126. 		    		u=p[u][i];
  127. 		    }
  128. 		    if(u==v)
  129. 		    	return u;
  130. 		    for(int i=log;i>=0;i--)
  131. 		    {
  132. 		    	if(p[u][i]!=-1 && p[u][i]!=p[v][i])
  133. 		    		{u=p[u][i];v=p[v][i];}
  134. 		    }
  135. 		    return p[u][0];
  136. 		}
  137. 		public static void Hld(int node,int cost,int par,ArrayList<Pair>[] tree,int[][] ecost)
  138. 		{
  139. 			if(chainhead[chainno]==-1)	chainhead[chainno]=node;
  140. 			pos++;
  141. 			chainind[node]=chainno;
  142. 			costarr[pos]=cost;
  143. 			arrpos[node]=pos;
  144. 			int hn=-1;int hc=0;
  145. 			for(int i=0;i<tree[node].size();i++)
  146. 			{
  147. 				int next=tree[node].get(i).v;
  148. 				if((next!=par)&&(hn==-1 || subsize[next]>subsize[hn]))
  149. 				{
  150. 					hn=next;
  151. 					hc=ecost[node][next];
  152. 				}
  153. 			}
  154. 			if(hn!=-1)
  155. 				Hld(hn,hc,node,tree,ecost);
  156. 			for(int i=0;i<tree[node].size();i++)
  157. 			{
  158. 				int next=tree[node].get(i).v;
  159. 				if(next!=par && next!=hn)
  160. 				{
  161. 					chainno++;
  162. 					Hld(next,ecost[node][next],node,tree,ecost);
  163. 				}
  164. 			}
  165. 		}
  166. 		public static void build(int node,int l,int r)
  167. 		{
  168. 			if(l==r)
  169. 			{
  170. 				segtree[node]=costarr[l];
  171. 			}
  172. 			else
  173. 			{
  174. 				int m=(l+r)/2;
  175. 				build((2*node),l,m);
  176. 				build((2*node)+1,m+1,r);
  177. 				segtree[node]=Math.max(segtree[2*node],segtree[2*node+1]);
  178. 			}
  179. 		}
  180. 		public static void update(int node,int l,int r,int ind,int val)
  181. 		{
  182. 			if(l==r)
  183. 			{
  184. 				costarr[ind]=val;
  185. 				segtree[node]=val;
  186. 			}
  187. 			else
  188. 			{
  189. 				int m=(l+r)/2;
  190. 				if(l<=ind && ind<=m)
  191. 				{
  192. 					update((2*node),l,m,ind,val);
  193. 				}
  194. 				else
  195. 				{
  196. 					update((2*node+1),m+1,r,ind,val);
  197. 				}
  198. 				segtree[node]=Math.max(segtree[2*node], segtree[2*node+1]);
  199. 			}
  200. 		}
  201. 		public static int query(int node,int l,int r,int s,int e)
  202. 		{
  203. 			if(e<l || r<s)
  204. 				return 0;
  205. 			if(s<=l && e>=r)
  206. 				return segtree[node];
  207. 			int m=(l+r)/2;
  208. 			int p1=query((2*node),l,m,s,e);
  209. 			int p2=query((2*node+1),m+1,r,s,e);
  210. 			return Math.max(p1, p2);
  211. 		}
  212. 		public static int querypath(int u,int v)
  213. 		{
  214. 			int lca=lca(u,v);
  215. 			return Math.max(queryup(u,lca), queryup(v,lca));
  216. 		}
  217. 		public static int queryup(int u,int v)
  218. 		{
  219. 			if(u==v)
  220. 				return 0;
  221. 			int lchain;int rchain=chainind[v];
  222. 			int ans=-1;
  223. 			while(true)
  224. 			{
  225. 				lchain=chainind[u];
  226. 				if(lchain==rchain)
  227. 				{
  228. 					if(u==v)
  229. 						break;
  230. 					int cur=query(1,1,pos,arrpos[v]+1,arrpos[u]);
  231. 					ans=Math.max(cur, ans);
  232. 					break;
  233. 				}
  234. 				int cur=query(1,1,pos,chainhead[lchain],arrpos[u]);
  235. 				ans=Math.max(cur,ans);
  236. 				u=chainhead[lchain];
  237. 				u=p[u][0];
  238. 			}
  239. 			return ans;
  240. 		}
  241. 		public static void update(int ind,int val)
  242. 		{
  243. 			int no=endnode[ind];
  244. 			update(1,1,pos,arrpos[no],val);
  245. 		}
  246. 	}
  247. 	private static class Pair implements Comparable<Pair>{
  248. 		int v,i;Pair j;
  249. 		public Pair(int a,int b){
  250. 			v=a;
  251. 			i=b;
  252. 		}
  253. 		public Pair(int a,Pair b)
  254. 		{
  255. 			v=a;
  256. 			j=b;
  257. 		}
  258. 		@Override
  259. 		public int compareTo(Pair arg0) {
  260. 			{
  261. 				return this.v-arg0.v;
  262. 			}
  263. 		}
  264. 	}
  265.  
  266. 	private static long pow(long a, long b, long c) {
  267. 		if (b == 0)
  268. 			return 1;
  269. 		long p = pow(a, b / 2, c);
  270. 		p = (p * p) % c;
  271. 		return (b % 2 == 0) ? p : (a * p) % c;
  272. 	}
  273. 	private static long gcd(long n, long l) {
  274. 		if (l == 0)
  275. 			return n;
  276. 		return gcd(l, n % l);
  277. 	}
  278.  
  279. 	private static long max(long a, long b) {
  280. 		if (a > b)
  281. 			return a;
  282. 		return b;
  283. 	}
  284.  
  285. 	private static long min(long a, long b) {
  286. 		if (a < b)
  287. 			return a;
  288. 		return b;
  289. 	}
  290.  
  291. 	public static void main(String[] args) throws Exception {
  292. 		new Thread(null,new Runnable(){
  293. 			@Override
  294. 			public void run() {
  295. 				/*try {
  296. 					InputReader(new FileInputStream("C:\\Users\\hardik\\Desktop\\C-small-1-attempt1.in"));
  297. 				} catch (FileNotFoundException e) {
  298. 					// TODO Auto-generated catch block
  299. 					e.printStackTrace();
  300. 				}*/
  301. 				InputReader(System.in);
  302. 				pw = new PrintWriter(System.out);
  303. 				/*try {
  304. 					pw=new PrintWriter(new FileOutputStream("C:\\Users\\hardik\\Desktop\\out.txt"));
  305. 				} catch (FileNotFoundException e) {
  306. 					// TODO Auto-generated catch block
  307. 					e.printStackTrace();
  308. 				}*/
  309. 				soln();
  310. 				pw.close();
  311. 			}
  312. 		},"1",1<<26).start();
  313. 	}
  314.  
  315. 	public static void InputReader(InputStream stream1) {
  316. 		stream = stream1;
  317. 	}
  318.  
  319. 	private static boolean isWhitespace(int c) {
  320. 		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  321. 	}
  322.  
  323. 	private static boolean isEndOfLine(int c) {
  324. 		return c == '\n' || c == '\r' || c == -1;
  325. 	}
  326.  
  327. 	private static int read() {
  328. 		if (numChars == -1)
  329. 			throw new InputMismatchException();
  330. 		if (curChar >= numChars) {
  331. 			curChar = 0;
  332. 			try {
  333. 				numChars = stream.read(buf);
  334. 			} catch (IOException e) {
  335. 				throw new InputMismatchException();
  336. 			}
  337. 			if (numChars <= 0)
  338. 				return -1;
  339. 		}
  340. 		return buf[curChar++];
  341. 	}
  342.  
  343. 	private static int ni() {
  344. 		int c = read();
  345. 		while (isSpaceChar(c))
  346. 			c = read();
  347. 		int sgn = 1;
  348. 		if (c == '-') {
  349. 			sgn = -1;
  350. 			c = read();
  351. 		}
  352. 		int res = 0;
  353. 		do {
  354. 			if (c < '0' || c > '9')
  355. 				throw new InputMismatchException();
  356. 			res *= 10;
  357. 			res += c - '0';
  358. 			c = read();
  359. 		} while (!isSpaceChar(c));
  360. 		return res * sgn;
  361. 	}
  362.  
  363. 	private static long nl() {
  364. 		int c = read();
  365. 		while (isSpaceChar(c))
  366. 			c = read();
  367. 		int sgn = 1;
  368. 		if (c == '-') {
  369. 			sgn = -1;
  370. 			c = read();
  371. 		}
  372. 		long res = 0;
  373. 		do {
  374. 			if (c < '0' || c > '9')
  375. 				throw new InputMismatchException();
  376. 			res *= 10;
  377. 			res += c - '0';
  378. 			c = read();
  379. 		} while (!isSpaceChar(c));
  380. 		return res * sgn;
  381. 	}
  382. 	private static double nd()
  383.     {
  384.         double ret = 0, div = 1;
  385.         int c = read();
  386.         while (c <= ' ')
  387.             c = read();
  388.         boolean neg = (c == '-');
  389.         if (neg)
  390.             c = read();
  391.  
  392.         do {
  393.             ret = ret * 10 + c - '0';
  394.         }
  395.         while ((c = read()) >= '0' && c <= '9');
  396.  
  397.         if (c == '.')
  398.         {
  399.             while ((c = read()) >= '0' && c <= '9')
  400.             {
  401.                 ret += (c - '0') / (div *= 10);
  402.             }
  403.         }
  404.  
  405.         if (neg)
  406.             return -ret;
  407.         return ret;
  408.     }
  409. 	private static String nextToken() {
  410. 		int c = read();
  411. 		while (isSpaceChar(c))
  412. 			c = read();
  413. 		StringBuilder res = new StringBuilder();
  414. 		do {
  415. 			res.appendCodePoint(c);
  416. 			c = read();
  417. 		} while (!isSpaceChar(c));
  418. 		return res.toString();
  419. 	}
  420.  
  421. 	private static String nli() {
  422. 		int c = read();
  423. 		while (isSpaceChar(c))
  424. 			c = read();
  425. 		StringBuilder res = new StringBuilder();
  426. 		do {
  427. 			res.appendCodePoint(c);
  428. 			c = read();
  429. 		} while (!isEndOfLine(c));
  430. 		return res.toString();
  431. 	}
  432.  
  433. 	private static int[] nia(int n) {
  434. 		int[] arr = new int[n];
  435. 		for (int i = 0; i < n; i++) {
  436. 			arr[i] = ni();
  437. 		}
  438. 		return arr;
  439. 	}
  440.  
  441. 	private static long[] nla(int n) {
  442. 		long[] arr = new long[n];
  443. 		for (int i = 0; i < n; i++) {
  444. 			arr[i] = nl();
  445. 		}
  446. 		return arr;
  447. 	}
  448.  
  449. 	private static void pa(int[] arr) {
  450. 		for (int i = 0; i < arr.length; i++) {
  451. 			pw.print(arr[i] + " ");
  452. 		}
  453. 		pw.println();
  454. 		return;
  455. 	}
  456.  
  457. 	private static void pa(long[] arr) {
  458. 		for (int i = 0; i < arr.length; i++) {
  459. 			pw.print(arr[i] + " ");
  460. 		}
  461. 		System.out.println();
  462. 		return;
  463. 	}
  464.  
  465. 	private static boolean isSpaceChar(int c) {
  466. 		if (filter != null)
  467. 			return filter.isSpaceChar(c);
  468. 		return isWhitespace(c);
  469. 	}
  470. 	private static char nc() {
  471. 		int c = read();
  472. 		while (isSpaceChar(c))
  473. 			c = read();
  474. 		char c1=(char)c;
  475. 		while(!isSpaceChar(c))
  476. 			c=read();
  477. 		return c1;
  478. 	}
  479. 	private interface SpaceCharFilter {
  480. 		public boolean isSpaceChar(int ch);
  481. 	}
  482. }
Success #stdin #stdout 0.09s 27980KB
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/lbmoC3
language:
Java (HotSpot 12)
created:
6 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!