query
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.
InputIn the first line there is an integer N (N <= 100000), in the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b [
] 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".OutputFor each "QUERY" operation, write one integer representing its result.
[c]Input:
4
1 3 5
3 4 10
3 2 7
QUERY 1 2
CHANGE 1 11
QUERY 4 1
DONE
4
1 3 5
3 4 10
3 2 7
QUERY 1 2
CHANGE 1 11
QUERY 4 1
DONE
Output:
7
11Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.