You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3…N-1.

We will ask you to perfrom some instructions of the following form:

  • CHANGE i ti : change the cost of the i-th edge to ti
  • QUERY a b : ask for the maximum edge cost on the path from node a to node b


The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.

For each test case:

  • In the first line there is an integer N (N <= 10000),
  • In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 1000000),
  • The next lines contain instructions “CHANGE i ti” or “QUERY a b”,
  • The end of each test case is signified by the string “DONE“.

There is one blank line between successive tests.


For each “QUERY” operation, write one integer representing its result.


1.29启程长沙的时候早晨起来敲的复习板子 洛谷到是很快A了 spoj死活过不去 菜死 知道今天才调过


spoj版: 注意多组数据需要针对重儿子和h数组清0 并且题目中给边的顺序不一定是按照深度小到深度大这样逐次给的而是乱序给的所以输出答案的时候注意判断一下


分类: 树链剖分


辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330