Problem Description

You are given a weighted tree with $n$ vertices. Its edges are $(u_1, v_1)$ (weight $w_1$), $(u_2, v_2)$ (weight $w_2$), $\dots$, $(u_{n-1}, v_{n-1})$ (weight $w_{n-1}$). Write a program to support $q$ queries, where each query is one of the following two types:

• Type 1: Given $x, k, n_1, \dots, n_k$, find the maximum path length from vertex $x$ to any vertex $y$, under the constraint that the path from $x$ to $y$ must not pass through any of the specified vertices $n_1, \dots, n_k$.
• Type 2: Given $i, w$, modify the weight of the $i$-th edge $(u_i, v_i)$ to $w$.

Input Format

Read an integer $n$ from the first line of standard input. The next $n - 1$ lines each contain three integers $u_i, v_i, w_i$, describing an edge connecting vertices $u_i$ and $v_i$ with weight $w_i$. The next line contains an integer $q$. Each of the following $q$ lines first gives the query type (1 or 2):

• If the type is 1, then read $x$, $k$, and $k$ integers $n_1, \dots, n_k$.
• If the type is 2, then read $i$ and $w$.

Output Format

For each type 1 query, print the required maximum path length on a separate line to standard output.

5
1 2 1
1 4 2
2 3 3
2 5 4
10
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 1 1 5
1 1 1 2
2 1 100
1 2 0
1 2 4 1 3 4 5

5
4
7
7
7
4
2
102
0

Hint

Sample 1 Explanation

In the queries, the target vertices that need to be found are, in order, $5, 5, 5, 3, 3, 4, 4, 2$.

Constraints

• $1 \le n, q,\ \sum k \le 200000$
• $1 \le u_i, v_i \le n$
• $1 \le w, w_i \le 10^9$
• For all $1 \le i \le k$, $n_i \ne x$
• For all $1 \le i \ne j \le k$, $n_i \ne n_j$

Subtasks

You can obtain the points for a subtask only if you pass all testdata for that subtask.

Translated by Qwen3.5-397B-A17B.

Translated by ChatGPT 5