说明

给定一棵包含 $n$ 个顶点的带权树，其边为 $(u_1, v_1)$（权重 $w_1$）、$(u_2, v_2)$（权重 $w_2$）、…、$(u_{n-1}, v_{n-1})$（权重 $w_{n-1}$）。请编写程序，支持 $q$ 次查询，每次查询属于以下两种类型之一：

• 类型 1：输入 $x, k, n_1, \dots, n_k$，要求找出从顶点 $x$ 到任意顶点 $y$ 的最长路径长度，其中路径从 $x$ 到 $y$ 不得经过任何被指定的顶点 $n_1, \dots, n_k$。
• 类型 2：输入 $i, w$，表示将第 $i$ 条边 $(u_i, v_i)$ 的权重修改为 $w$。

输入格式

从标准输入的第一行读入整数 $n$。接下来的 $n - 1$ 行，每行包含三个整数 $u_i, v_i, w_i$，表示连接顶点 $u_i$ 和 $v_i$ 的一条边，其权重为 $w_i$。再下一行读入整数 $q$。随后的 $q$ 行中，每行首先给出查询类型（1 或 2）：

• 若类型为 1，则接着读入 $x$、$k$，以及 $k$ 个整数 $n_1, \dots, n_k$；
• 若类型为 2，则接着读入 $i$ 和 $w$。

输出格式

对于每个类型 1 的查询，在标准输出上单独一行打印所求的最长路径长度。

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

提示

样例 1 解释

在查询中需要寻找的目标顶点依次是 $5, 5, 5, 3, 3, 4, 4, 2$。

限制条件

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

子任务

只有当成功通过某子任务所对应的所有测试点时，才能获得该子任务的分数。

翻译由 Qwen3.5-397B-A17B 完成