Dynamic Tree Maximum Edge Query

Given a tree with \(n\) nodes and \(n-1\) edges, each edge has an associated weight. You are asked to perform two types of operations:

• CHANGE i t: Change the weight of the \(i\)-th edge to \(t\).
• QUERY a b: Find and output the maximum edge weight on the unique path from node \(a\) to node \(b\). When \(a = b\), output \(0\).

The edges are given in the order of their indices (from \(1\) to \(n-1\)). For the purpose of the CHANGE operation, it is guaranteed that \(i\) is a valid edge index. Note that the tree is undirected and the nodes are numbered from \(1\) to \(n\).

inputFormat

The first line contains an integer \(n\), the number of nodes in the tree.

The next \(n-1\) lines each contain three integers \(u\), \(v\), and \(w\), describing an edge between nodes \(u\) and \(v\) with weight \(w\). The edges are indexed from \(1\) to \(n-1\) in the order they are given.

The following line contains an integer \(m\), the number of operations.

Each of the next \(m\) lines contains an operation in one of the following forms:

• CHANGE i t
• QUERY a b

It is guaranteed that all operations are valid. When \(a = b\) in a query, output \(0\).

outputFormat

For each QUERY operation, output the maximum edge weight on the path from node \(a\) to node \(b\) on a new line.

sample

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

3
2