QTREE - Query on a tree

给定 $n$ 个点的树，边按输入顺序编号为 $1,2, \ldots, n-1$，要求作以下操作： - `CHANGE i ti` 将第 $i$ 条边权值改为 $t_i$； - `QUERY a b` 询问从 $a$ 点到 $b$ 点路径上的最大边权。 有多组测试数据，每组数据以 `DONE` 结尾。 感谢@vegacx 提供的翻译

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

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

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

1
3