fork download
copy 
  1. import java.io.*;
  2. import java.math.*;
  3. import java.util.*;
  4.  
  5.  
  6. /**
  7.  *
  8.  * @author Saju
  9.  *
  10.  */
  11.  
  12. public class Main {
  13.  
  14.     private static int dx[] = { 1, 0, -1, 0 };
  15.     private static int dy[] = { 0, -1, 0, 1 };
  16.  
  17.     private static final long INF = Long.MAX_VALUE;
  18.     private static final int INT_INF = Integer.MAX_VALUE;
  19.     private static final long NEG_INF = Long.MIN_VALUE;
  20.     private static final int NEG_INT_INF = Integer.MIN_VALUE;
  21.     private static final double EPSILON = 1e-10;
  22.  
  23.     private static final int MAX = 10001;
  24.  
  25.     private static final long MOD = 1000000007;
  26.  
  27.     private static final int MAXN = 10000007;
  28.     private static final int MAXA = 10000009;
  29.     private static final int MAXLOG = 22;
  30.  
  31. 	public static void main(String[] args) throws IOException {
  32.  
  33. 		InputReader in = new InputReader(System.in);
  34. 		PrintWriter out = new PrintWriter(System.out);
  35.  
  36. //         InputReader in = new InputReader(new FileInputStream("src/test.in"));
  37. //         PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("src/test.out")));
  38.  
  39. /*
  40.  
  41.  
  42. 2
  43.  
  44. 3
  45. 1 2 1
  46. 2 3 2
  47. QUERY 1 2
  48. CHANGE 1 3
  49. QUERY 1 2
  50. DONE
  51.  
  52. 3
  53. 1 2 1
  54. 2 3 2
  55. QUERY 1 2
  56. CHANGE 1 3
  57. QUERY 1 2
  58. DONE
  59.  
  60. */
  61.  
  62. 		int test = in.nextInt();
  63. 		StringBuilder sb = new StringBuilder();
  64. 		HLD hld = new HLD();
  65. 		for (int t = 1; t <= test; t++) {
  66. 			int n = in.nextInt();
  67. 			hld.vertex = n;
  68. 			hld.clear();
  69. 			for(int i = 1; i <= n - 1; i++) {
  70. 				int u = in.nextInt();
  71. 				int v = in.nextInt();
  72. 				int w = in.nextInt();
  73. 				hld.addEdge(u, v, w, i);
  74. 			}
  75. 			hld.buildHLD();
  76.  
  77. 			while(true) {
  78. 				String str = in.next();
  79. 				if(str.charAt(0) == 'D') {
  80. 					break;
  81. 				}
  82.  
  83. 				int x = in.nextInt();
  84. 				int y = in.nextInt();
  85. 				if(str.charAt(0) == 'Q') {
  86. //					out.println(query(x, y));
  87. 					sb.append(hld.query(x, y) + "\n");
  88. 				}
  89. 				else {
  90. 					hld.update(x, y);;
  91. 				}
  92. 			}
  93. 		}
  94. 		out.print(sb.toString());
  95.  
  96.  
  97. 		out.flush();
  98. 		out.close();
  99. 		System.exit(0);
  100. 	}
  101.  
  102. 	private static class HLD {
  103. 		final int MAX = 10001;
  104. 		final int MAXLOG = 15;
  105.  
  106. 		int vertex;
  107. 		List<Edge> adj[] = new ArrayList[MAX];
  108. 		int[][] pp = new int[MAXLOG][MAX];
  109. 		int[] level = new int[MAX];
  110. 		int[] tree = new int[MAX << 2];
  111. 		int[] twoPower = new int[MAXLOG];
  112.  
  113. 		int chainNo;
  114. 		int indexNo;
  115. 		int[] chainHead = new int[MAX];
  116. 		int[] chainSize = new int[MAX];
  117. 		int[] nodeInWhichChain = new int[MAX];
  118. 		int[] nodeIndexInBaseArray = new int[MAX];
  119. 		int[] baseArray = new int[MAX];
  120. 		int[] edgeIndex = new int[MAX];
  121. 		int[] subtreeSize = new int[MAX];
  122.  
  123. 		public HLD() {
  124. 			for (int i = 0; i < MAX; i++) {
  125. 				adj[i] = new ArrayList<>();
  126. 			}
  127. 			twoPower[0] = 1;
  128. 			for (int i = 1; i < MAXLOG; i++) {
  129. 				twoPower[i] = twoPower[i - 1] << 1;
  130. 			}
  131. 		}
  132.  
  133. 		public void clear() {
  134. 			for (int i = 1; i <= vertex; i++) {
  135. 				adj[i].clear();
  136. 			}
  137. 			for (int i = 1; i <= vertex; i++) {
  138. 				chainHead[i] = -1;
  139. 				chainSize[i] = -1;
  140. 			}
  141.  
  142. 			for (int i = 0; i < MAXLOG; i++) {
  143. 				for (int j = 1; j <= vertex; j++) {
  144. 					pp[i][j] = -1;
  145. 				}
  146. 			}
  147. 		}
  148.  
  149. 		public void addEdge(int u, int v, int w, int idx) {
  150. 			adj[u].add(new Edge(v, w, idx));
  151. 			adj[v].add(new Edge(u, w, idx));
  152. 		}
  153.  
  154. 		public void buildHLD() {
  155.  
  156. 			indexNo = 0;
  157. 			chainNo = 1;
  158. 			dfs(1, -1, 0);
  159. 			sparseTable();
  160. 			hld(1, -1, 0);
  161. 			build(1, 1, vertex);
  162. 		}
  163.  
  164. 		public void update(int idx, int val) {
  165. 			update(1, 1, vertex, edgeIndex[idx], val);
  166. 		}
  167.  
  168. 		public int query(int u, int v) {
  169. 			int lca = lca(u, v);
  170. 			int val1 = hldQuery(lca, u);
  171. 			int val2 = hldQuery(lca, v);
  172. 			return max(val1, val2);
  173. 		}
  174.  
  175. 		private int hldQuery(int u, int v) {
  176. 			if (u == v) {
  177. 				return 0;
  178. 			}
  179.  
  180. 			int ans = 0;
  181. 			while (true) {
  182. 				if (nodeInWhichChain[u] == nodeInWhichChain[v]) {
  183. 					int start = nodeIndexInBaseArray[u];
  184. 					int end = nodeIndexInBaseArray[v];
  185. 					if (start < end) {
  186. 						ans = max(ans, query(1, 1, vertex, start + 1, end));
  187. 					}
  188. 					return ans;
  189. 				}
  190. 				int head = chainHead[nodeInWhichChain[v]];
  191. 				int start = nodeIndexInBaseArray[head];
  192. 				int end = nodeIndexInBaseArray[v];
  193. 				ans = max(ans, query(1, 1, vertex, start, end));
  194. 				v = pp[0][head];
  195. 			}
  196. 		}
  197.  
  198. 		private void dfs(int u, int parent, int d) {
  199. 			pp[0][u] = parent;
  200. 			subtreeSize[u] = 1;
  201. 			level[u] = d;
  202. 			for (Edge e : adj[u]) {
  203. 				if (e.v != parent) {
  204. 					dfs(e.v, u, d + 1);
  205. 					subtreeSize[u] += subtreeSize[e.v];
  206. 				}
  207. 			}
  208. 		}
  209.  
  210. 		private void sparseTable() {
  211. 			for (int i = 1; i < MAXLOG; i++) {
  212. 				for (int j = 1; j <= vertex; j++) {
  213. 					if (pp[i - 1][j] != -1) {
  214. 						pp[i][j] = pp[i - 1][pp[i - 1][j]];
  215. 					}
  216. 				}
  217. 			}
  218. 		}
  219.  
  220. 		private void hld(int u, int parent, int cost) {
  221.  
  222. 			indexNo++;
  223. 			nodeIndexInBaseArray[u] = indexNo;
  224. 			nodeInWhichChain[u] = chainNo;
  225. 			baseArray[indexNo] = cost;
  226. 			chainSize[chainNo]++;
  227. 			if (chainHead[chainNo] == -1) {
  228. 				chainHead[chainNo] = u;
  229. 			}
  230.  
  231. 			int specialChild = -1;
  232. 			int specialCost = -1;
  233. 			int specialIdx = -1;
  234. 			int maxSubtreeSize = 0;
  235.  
  236. 			for (Edge e : adj[u]) {
  237. 				int v = e.v;
  238. 				if (v != parent) {
  239. 					if (maxSubtreeSize < subtreeSize[v]) {
  240. 						maxSubtreeSize = subtreeSize[v];
  241. 						specialChild = v;
  242. 						specialCost = e.w;
  243. 						specialIdx = e.idx;
  244. 					}
  245. 				}
  246. 			}
  247.  
  248. 			if (specialChild != -1) {
  249. 				edgeIndex[specialIdx] = indexNo + 1;
  250. 				hld(specialChild, u, specialCost);
  251. 			}
  252.  
  253. 			for (Edge e : adj[u]) {
  254. 				int v = e.v;
  255. 				if (v != parent && v != specialChild) {
  256. 					chainNo++;
  257. 					edgeIndex[e.idx] = indexNo + 1;
  258. 					hld(v, u, e.w);
  259. 				}
  260. 			}
  261. 		}
  262.  
  263. 		private void build(int node, int left, int right) {
  264. //			System.out.println(left + " " + right);
  265. 			if (left == right) {
  266. 				tree[node] = baseArray[left];
  267. 				return;
  268. 			}
  269.  
  270. 			int mid = (left + right) >> 1;
  271. 			int leftNode = node << 1;
  272. 			int rightNode = leftNode | 1;
  273. 			build(leftNode, left, mid);
  274. 			build(rightNode, mid + 1, right);
  275. 			tree[node] = max(tree[leftNode], tree[rightNode]);
  276. 		}
  277.  
  278. 		private void update(int node, int left, int right, int idx, int val) {
  279. 			if (left == right && idx == left) {
  280. 				tree[node] = val;
  281. 			} else {
  282. 				int mid = (left + right) >> 1;
  283. 				int leftNode = node << 1;
  284. 				int rightNode = leftNode | 1;
  285. 				if (idx <= mid) {
  286. 					update(leftNode, left, mid, idx, val);
  287. 				} else {
  288. 					update(rightNode, mid + 1, right, idx, val);
  289. 				}
  290. 				tree[node] = max(tree[leftNode], tree[rightNode]);
  291. 			}
  292. 		}
  293.  
  294. 		private int query(int node, int left, int right, int start, int end) {
  295.  
  296. 			if (left > right || left > end || right < start) {
  297. 				return 0;
  298. 			}
  299.  
  300. 			if (left >= start && right <= end) {
  301. 				return tree[node];
  302. 			}
  303.  
  304. 			int mid = (left + right) >> 1;
  305. 			int leftNode = node << 1;
  306. 			int rightNode = leftNode | 1;
  307. 			int val1 = query(leftNode, left, mid, start, end);
  308. 			int val2 = query(rightNode, mid + 1, right, start, end);
  309.  
  310. 			return max(val1, val2);
  311. 		}
  312.  
  313. 		private int lca(int p, int q) {
  314.  
  315. 			if(p == q) {
  316. 				return p;
  317. 			}
  318.  
  319. 			if (level[p] < level[q]) {
  320. 				int temp = p;
  321. 				p = q;
  322. 				q = temp;
  323. 			}
  324.  
  325. 			for (int i = MAXLOG - 1; i >= 0; i--) {
  326. 				if ((level[p] - twoPower[i]) >= level[q]) {
  327. 					p = pp[i][p];
  328. 				}
  329. 			}
  330. 			if (p == q) {
  331. 				return p;
  332. 			}
  333.  
  334. 			for (int i = MAXLOG - 1; i >= 0; i--) {
  335. 				if (pp[i][p] != pp[i][q] && pp[i][p] != -1) {
  336. 					p = pp[i][p];
  337. 					q = pp[i][q];
  338. 				}
  339. 			}
  340. 			return pp[0][p];
  341. 		}
  342.  
  343. 		private static class Edge {
  344. 			int v;
  345. 			int w;
  346. 			int idx;
  347.  
  348. 			Edge() {
  349.  
  350. 			}
  351.  
  352. 			Edge(int v, int w, int idx) {
  353. 				this.v = v;
  354. 				this.w = w;
  355. 				this.idx = idx;
  356. 			}
  357. 		}
  358. 	}
  359.  
  360.     private static long bigMod(long n, long k, long m) {
  361.  
  362.         long ans = 1;
  363.         while (k > 0) {
  364.             if ((k & 1) == 1) {
  365.                 ans = (ans * n) % m;
  366.             }
  367.             n = (n * n) % m;
  368.             k >>= 1;
  369.         }
  370.         return ans;
  371.     }
  372.  
  373.     private static int ceil(int n, int x) {
  374.         int div = n / x;
  375.         if(div * x != n) {
  376.             div++;
  377.         }
  378.         return div;
  379.     }
  380.  
  381.     private static class Point {
  382.         double x;
  383.         double y;
  384.  
  385.         Point(double x, double y) {
  386.             this.x = x;
  387.             this.y = y;
  388.         }
  389.  
  390.         double getDistance(Point p2) {
  391.             Point p1 = this;
  392.             double dx = p1.x - p2.x;
  393.             double dy = p1.y - p2.y;
  394.  
  395.             return Math.sqrt((dx * dx) + (dy * dy));
  396.         }
  397.     }
  398.  
  399.     private static int abs(int x) {
  400.         if (x < 0) {
  401.             return -x;
  402.         }
  403.         return x;
  404.     }
  405.  
  406.     private static long abs(long x) {
  407.         if(x < 0) {
  408.             return -x;
  409.         }
  410.         return x;
  411.     }
  412.  
  413.     private static int lcm(int a, int b) {
  414.         return (a * b) / gcd(a, b);
  415.     }
  416.  
  417.     private static int gcd(int a, int b) {
  418.         if (a == 0)
  419.             return b;
  420.         return gcd(b % a, a);
  421.     }
  422.  
  423.     private static int log(long x, int base) {
  424.         return (int) (Math.log(x) / Math.log(base));
  425.     }
  426.  
  427.     private static long min(long a, long b) {
  428.         if (a < b) {
  429.             return a;
  430.         }
  431.         return b;
  432.     }
  433.  
  434.     private static int min(int a, int b) {
  435.         if (a < b) {
  436.             return a;
  437.         }
  438.         return b;
  439.     }
  440.  
  441.     private static long max(long a, long b) {
  442.         if (a < b) {
  443.             return b;
  444.         }
  445.         return a;
  446.     }
  447.  
  448.     private static int max(int a, int b) {
  449.         if (a < b) {
  450.             return b;
  451.         }
  452.         return a;
  453.     }
  454.  
  455.     private static class InputReader {
  456.         public BufferedReader reader;
  457.         public StringTokenizer tokenizer;
  458.  
  459.         public InputReader(InputStream stream) {
  460.             reader = new BufferedReader(new InputStreamReader(stream));
  461.             tokenizer = null;
  462.         }
  463.  
  464.         public String next() {
  465.             try {
  466.                 while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  467.                     tokenizer = new StringTokenizer(reader.readLine());
  468.  
  469.                 }
  470.             } catch (IOException e) {
  471.                 return null;
  472.             }
  473.             return tokenizer.nextToken();
  474.         }
  475.  
  476.         public String nextLine() {
  477.             String line = null;
  478.             try {
  479.                 tokenizer = null;
  480.                 line = reader.readLine();
  481.             } catch (IOException e) {
  482.                 throw new RuntimeException(e);
  483.             }
  484.             return line;
  485.         }
  486.  
  487.         public int nextInt() {
  488.             return Integer.parseInt(next());
  489.         }
  490.  
  491.         public double nextDouble() {
  492.             return Double.parseDouble(next());
  493.         }
  494.  
  495.         public long nextLong() {
  496.             return Long.parseLong(next());
  497.         }
  498.  
  499.         public boolean hasNext() {
  500.             try {
  501.                 while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  502.                     tokenizer = new StringTokenizer(reader.readLine());
  503.                 }
  504.             } catch (Exception e) {
  505.                 return false;
  506.             }
  507.             return true;
  508.         }
  509.     }
  510. }
  511.  
Success #stdin #stdout 0.08s 35632KB
comments (?)
stdin
copy 
2

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
stdout
copy 
1
3
1
3
https://ideone.com/kIH2N5
language:
Java (HotSpot 12)
created:
3 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!