fork(1) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.File;
  3. import java.io.FileNotFoundException;
  4. import java.io.FileReader;
  5. import java.io.IOException;
  6. import java.io.InputStream;
  7. import java.io.InputStreamReader;
  8. import java.io.PrintWriter;
  9. import java.util.ArrayList;
  10. import java.util.Arrays;
  11. import java.util.HashMap;
  12. import java.util.Hashtable;
  13. import java.util.List;
  14. import java.util.Map;
  15. import java.util.Random;
  16. import java.util.StringTokenizer;
  17.  
  18.  class HeavyLightNoRecursion {
  19.  
  20. 	segmentTree value[];
  21.  
  22. 	List<Integer>[] tree;
  23. 	int[] size;
  24. 	int[] parent;
  25. 	int[] tin;
  26. 	int[] tout;
  27. 	int time;
  28. 	int[] path;
  29. 	int[] pathSize;
  30. 	int[] pathPos;
  31. 	int[] pathRoot;
  32. 	int pathCount;
  33. 	int len1;
  34. 	int[][] up;
  35.  
  36.  
  37. 	public HeavyLightNoRecursion(List<Integer>[] tree) {
  38. 		this.tree = tree;
  39. 		int n = tree.length;
  40.  
  41. 		size = new int[n];
  42. 		parent = new int[n];
  43. 		tin = new int[n];
  44. 		tout = new int[n];
  45.  
  46. 		len1 = 1;
  47. 		while ((1 << len1) <= n) ++len1;
  48. 		up = new int[len1][n];
  49.  
  50. 		calcSizeParentTinTout(0);
  51.  
  52. 		path = new int[n];
  53. 		pathSize = new int[n];
  54. 		pathPos = new int[n];
  55. 		pathRoot = new int[n];
  56. 		buildPaths(0);
  57.  
  58. 		value=new segmentTree[pathCount];
  59. 		for (int i = 0; i < pathCount; i++) {
  60. 			int m = pathSize[i];
  61.  
  62. 			value[i]=new segmentTree(new long[m]);
  63. 		}
  64. 	}
  65.  
  66. 	class segmentTree
  67. 	{
  68. 		int n;  // array size
  69. 		long t[];
  70.  
  71. 		public segmentTree(long[] arr)
  72. 		{
  73. 			n=arr.length;
  74. 			t=new long[3*n];
  75. 			for(int i=0;i<n;i++)
  76. 			{
  77. 				t[n+i]=arr[i];
  78. 			}
  79. 			build();
  80. 		}
  81.  
  82. 		void build() {  // build the tree
  83. 			for (int i = n - 1; i > 0; --i) t[i] = Math.max(t[i<<1],t[i<<1|1]);
  84. 		}
  85.  
  86. 		void modify(int p, long value) { 
  87. 			for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = Math.max(t[p],t[p^1]);
  88. 		}
  89.  
  90. 		long query(int l, int r) {  // sum on interval [l, r)
  91. 			long res = 0;
  92. 			for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  93. 				if ((l&1)!=0) res=Math.max(res , t[l++]);
  94. 				if ((r&1)!=0) res= Math.max(res, t[--r]);
  95. 			}
  96. 			return res;
  97. 		}
  98. 	}
  99.  
  100. 	int query_up(int u, int v) {
  101. 		if(u == v) return 0; 
  102.  
  103. 		int uchain, vchain = path[v], ans = -1;
  104.  
  105. 		while(true) {
  106.  
  107. 			uchain = path[u];
  108. 			if(uchain == vchain) {
  109.  
  110. 				if(u==v) break;
  111. 				ans=(int) Math.max(value[path[u]].query( pathPos[v]+1,pathPos[u]+1),ans);
  112.  
  113. 				break;
  114. 			}
  115. 			ans=(int) Math.max(value[path[u]].query(0,pathPos[u]+1),ans);
  116.  
  117. 			u = pathRoot[uchain]; // move u to u's chainHead
  118. 			u = parent[u]; //Then move to its parent, that means we changed chains
  119. 		}
  120. 		return ans;
  121. 	}
  122.  
  123.  
  124. 	int query(int u, int v) {
  125. 		/*
  126. 		 * We have a query from u to v, we break it into two queries, u to LCA(u,v) and LCA(u,v) to v
  127. 		 */
  128. 		int lca = lca(u, v);
  129. 		int ans = query_up(u, lca); // One part of path
  130. 		int temp = query_up(v, lca); // another part of path
  131. 		if(temp > ans) ans = temp; // take the maximum of both paths
  132. 		return ans;
  133. 	}
  134.  
  135. 	void calcSizeParentTinTout(int root) {
  136. 		int n = tree.length;
  137. 		int[] curEdge = new int[n];
  138. 		int[] stack = new int[n];
  139. 		stack[0] = root;
  140. 		parent[root] = root;
  141. 		for (int top = 0; top >= 0; ) {
  142. 			int u = stack[top];
  143. 			if (curEdge[u] == 0) {
  144.  
  145. 				//from
  146. 				up[0][u] = parent[u];
  147. 				for (int i = 1; i < len1; i++)
  148. 					up[i][u] = up[i - 1][up[i - 1][u]];
  149. 				//to
  150.  
  151. 				tin[u] = time++;
  152. 				size[u] = 1;
  153. 			}
  154. 			if (curEdge[u] < tree[u].size()) {
  155. 				int v = tree[u].get(curEdge[u]++);
  156. 				if (curEdge[v] == 0) {
  157. 					stack[++top] = v;
  158. 					parent[v] = u;
  159. 				}
  160. 			} else {
  161. 				--top;
  162. 				if (parent[u] != u)
  163. 					size[parent[u]] += size[u];
  164. 				tout[u] = time++;
  165. 			}
  166. 		}
  167. 		parent[root]=-1;
  168. 	}
  169.  
  170. 	int newPath(int u) {
  171. 		pathRoot[pathCount] = u;
  172. 		return pathCount++;
  173. 	}
  174.  
  175. 	void buildPaths(int root) {
  176. 		int n = tree.length;
  177. 		int[] curEdge = new int[n];
  178. 		int[] stackPath = new int[n];
  179. 		int[] stack = new int[n];
  180. 		stack[0] = root;
  181. 		stackPath[0] = newPath(root);
  182. 		for (int top = 0; top >= 0; ) {
  183. 			int u = stack[top];
  184. 			int path = stackPath[top];
  185. 			if (curEdge[u] == 0) {
  186. 				this.path[u] = path;
  187. 				pathPos[u] = pathSize[path]++;
  188. 			}
  189. 			if (curEdge[u] < tree[u].size()) {
  190. 				int v = tree[u].get(curEdge[u]++);
  191. 				if (curEdge[v] == 0) {
  192. 					stack[++top] = v;
  193. 					stackPath[top] = 2 * size[v] >= size[u] ? path : newPath(v);
  194. 				}
  195. 			} else {
  196. 				--top;
  197. 			}
  198. 		}
  199. 	}
  200.  
  201. 	void buildPaths(int u, int path) {
  202. 		this.path[u] = path;
  203. 		pathPos[u] = pathSize[path]++;
  204. 		for (int v : tree[u]) {
  205. 			if (v != parent[u])
  206. 				buildPaths(v, 2 * size[v] >= size[u] ? path : newPath(v));
  207. 		}
  208. 	}
  209.  
  210.  
  211.  
  212. 	boolean isAncestor(int p, int ch) {
  213. 		return tin[p] <= tin[ch] && tout[ch] <= tout[p];
  214. 	}
  215.  
  216. 	void change(int ver, int val) {
  217. 		int pa=path[ver];
  218. 		int pospa=pathPos[ver];
  219. 		value[pa].modify(pospa, val);
  220. 	}
  221.  
  222.  
  223. 	public int lca(int a, int b) {
  224. 		if (isAncestor(a, b))
  225. 			return a;
  226. 		if (isAncestor(b, a))
  227. 			return b;
  228. 		for (int i = len1 - 1; i >= 0; i--)
  229. 			if (!isAncestor(up[i][a], b))
  230. 				a = up[i][a];
  231.  
  232. 		return up[0][a];
  233. 	}
  234.  
  235. 	public static void main(String[] args) 
  236. 	{
  237. 		FastScanner in=new FastScanner(System.in);
  238. 		PrintWriter out=new PrintWriter(System.out);
  239. 		in.nextInt();
  240. 		int n=in.nextInt();
  241. 		Hashtable<Long, Integer> edgew=new Hashtable<>();
  242. 		Hashtable<Integer, Long> edgeidx=new Hashtable<>();
  243. 		ArrayList<Integer>[] arr=new ArrayList[n];
  244. 		for(int i=0;i<n;i++)
  245. 		{
  246. 			arr[i]=new ArrayList<Integer>();
  247. 		}
  248.  
  249. 		for(int e=1;e<=(n-1);e++)
  250. 		{
  251. 			int a=in.nextInt()-1;
  252. 			int b=in.nextInt()-1;
  253. 			int c=in.nextInt();
  254. 			long imge=edge(a,b);
  255. 			edgew.put(imge,c);
  256. 			edgeidx.put(e, imge);
  257. 			arr[a].add(b);
  258. 			arr[b].add(a);
  259. 		}
  260.  
  261.  
  262. 		HeavyLightNoRecursion hdl=new HeavyLightNoRecursion(arr);
  263.  
  264.  
  265. 		for(int i=1;i<=n-1;i++)
  266. 		{
  267. 			long ab=edgeidx.get(i);
  268. 			int a=(int)(ab>>32);
  269. 			int b=(int)((ab<<32)>>32);
  270. 			if(hdl.parent[a]==b)
  271. 			{
  272. 				hdl.change(a, edgew.get(ab));
  273. 			}
  274. 			else
  275. 			{
  276. 				hdl.change(b, edgew.get(ab));
  277. 			}
  278. 		}
  279. 		l:
  280. 		while(true)
  281. 		{
  282. 			switch(in.next())
  283. 			{
  284. 			case "QUERY":
  285. 				int a1=in.nextInt()-1;
  286. 				int b1=in.nextInt()-1;
  287. 				out.println(hdl.query(a1,b1));
  288. 			break;
  289. 			case "CHANGE":
  290. 				int i=in.nextInt();
  291. 				int w=in.nextInt();
  292. 				long ab=edgeidx.get(i);
  293. 				int a=(int)(ab>>32);
  294. 				int b=(int)((ab<<32)>>32);
  295. 				edgew.put(ab, w);
  296. 				if(hdl.parent[a]==b)
  297. 				{
  298. 					hdl.change(a,  edgew.get(ab));
  299. 				}
  300. 				else
  301. 				{
  302. 					hdl.change(b, edgew.get(ab));
  303. 				}
  304. 			break;
  305. 			default:
  306. 				break l;
  307. 			}
  308. 		}
  309. 		out.close();
  310. 	}
  311.  
  312. 	static long edge(int u, int v) {
  313. 		return ((long) Math.min(u, v) << 32) + Math.max(u, v);
  314. 	}
  315.  
  316.  
  317. 	static class FastScanner {
  318. 		BufferedReader br;
  319. 		StringTokenizer st;
  320.  
  321. 		public FastScanner(File f) {
  322. 			try {
  323. 				br = new BufferedReader(new FileReader(f));
  324. 			} catch (FileNotFoundException e) {
  325. 				e.printStackTrace();
  326. 			}
  327. 		}
  328.  
  329. 		public FastScanner(InputStream f) {
  330. 			br = new BufferedReader(new InputStreamReader(f));
  331. 		}
  332.  
  333. 		String next() {
  334. 			while (st == null || !st.hasMoreTokens()) {
  335. 				String s = null;
  336. 				try {
  337. 					s = br.readLine();
  338. 				} catch (IOException e) {
  339. 					e.printStackTrace();
  340. 				}
  341. 				if (s == null)
  342. 					return null;
  343. 				st = new StringTokenizer(s);
  344. 			}
  345. 			return st.nextToken();
  346. 		}
  347.  
  348. 		boolean hasMoreTokens() {
  349. 			while (st == null || !st.hasMoreTokens()) {
  350. 				String s = null;
  351. 				try {
  352. 					s = br.readLine();
  353. 				} catch (IOException e) {
  354. 					e.printStackTrace();
  355. 				}
  356. 				if (s == null)
  357. 					return false;
  358. 				st = new StringTokenizer(s);
  359. 			}
  360. 			return true;
  361. 		}
  362.  
  363. 		int nextInt() {
  364. 			return Integer.parseInt(next());
  365. 		}
  366.  
  367. 		long nextLong() {
  368. 			return Long.parseLong(next());
  369. 		}
  370.  
  371. 		double nextDouble() {
  372. 			return Double.parseDouble(next());
  373. 		}
  374. 	}
  375. }
  376.  
  377.  
Success #stdin #stdout 0.12s 320576KB
comments (?)
stdin
copy 
1
15
1 2 5
1 4 15
1 10 10
2 3 11
2 5 3
5 9 4
9 15 5
3 11 12
3 6 14
6 7 20
6 8 21
8 12 1
12 13 2
13 14 3
QUERY 4 11
QUERY 7 10
QUERY 15 12
DONE
stdout
copy 
15
20
21
https://ideone.com/DBrQxm
language:
Java (HotSpot 12)
created:
10 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!