P15842 [Bulgarian NOI 2024] 最长路径 / longest

给定一棵包含 $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 的查询，在标准输出上单独一行打印所求的最长路径长度。

### 样例 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$ ### 子任务 | 子任务 | 分数 | 额外限制条件 | |:------:|:----:|:------------:| | $1$ | $5$ | $n, q \le 5000$ | | $2$ | $15$ | 每个顶点的度数至多为 $2$ | | $3$ | $15$ | $k = 0$ | | $4$ | $30$ | 不存在类型 $2$ 的查询 | | $5$ | $35$ | 无 | 只有当成功通过某子任务所对应的所有测试点时，才能获得该子任务的分数。 翻译由 Qwen3.5-397B-A17B 完成