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
1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
输出样例 #1
1
3