Background

The constraints differ from those on SPOJ.

Problem Description

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$.

Input Format

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.

Output Format

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

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

1
3

Hint

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