P4114 Qtree1

The constraints differ from those on SPOJ.

Given a tree with $n$ nodes, there are two operations: - `CHANGE i t` set the weight of the $i$-th edge to $t$. - `QUERY a b` output the maximum edge weight on the path from $a$ to $b$. When $a = b$, output $0$.

The first line contains an integer $n$, the number of nodes. Lines $2$ through $n$ each contain three integers $u, v, w$, indicating that there is an edge between $u$ and $v$ with weight $w$. Starting from line $n + 1$, there are an unspecified number of lines. Each line starts with a string, which can be one of: - `CHANGE` followed by two integers $x, t$, indicating an update operation. - `QUERY` followed by two positive integers $a, b$, indicating a query operation. - `DONE` indicating the end of input.

For each `QUERY` operation, output one line with a single number: the maximum edge weight on the path between $a$ and $b$.

Constraints For all test points, it is guaranteed that: - $1 \leq n \leq 10^5$. - $1 \leq u, v, a, b \leq n$, $1 \leq x < n$. - $1 \leq w, t \leq 2^{31} - 1$. - The number of operations does not exceed $3 \times 10^5$. Translated by ChatGPT 5