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
    or
  • QUERY a b : ask for the maximum edge cost on the path from node a to node b

Input

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.

Output

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

Example

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

洛谷:洛谷数据比较水..建议写过之后再去spoj挑战下

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

 

分类: 树链剖分

elijahqi

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

发表评论