Tree and Query 21

The tree has $N$ vertices numbered from $0$ to $N-1$. Each edge has a non-negative integer weight.

Process the following two kinds of queries.

• 1 u v w x: Remove the edge between $u$ and $v$, then add an edge with weight $x$ between $v$ and $w$. An edge between $u$ and $v$ is guaranteed to exist. The graph is guaranteed to remain a tree after the operation. ($0 \le x \le 100\,000$)
• 2 k x1 x2 ... xk: For the vertices $x_1, x_2, \ldots, x_k$, consider the unique simple path between $x_i$ and $x_j$ for every $1 \le i < j \le k$. Print the sum of the weights of all edges in the union of these simple paths. All $x_i$ are distinct. ($1 \le k \le n$)

The first line contains $N$, the size of the tree. ($2 \le N \le 100\,000$)

Each of the next $N-1$ lines contains three integers $u$, $v$, and $w$, meaning there is an edge of weight $w$ between vertices $u$ and $v$. ($0 \le u, v \le N-1$, $0 \le w \le 100\,000$)

The next line contains $Q$, the number of queries. ($1 \le Q \le 100\,000$)

The next $Q$ lines contain the queries described above.

The sum of $k$ over all type 2 queries is between 1 and 100,000, inclusive.

For each type 2 query, print the answer on its own line, in the order the queries appear.