P16826 [AFOI 2025] C.道路修复

你是参加 CSP-S 2025 的一位参赛者，你受 $n=1000$ 的大样例误导认为 $O(2^km \log m)$ 的暴力可以通过这题。 在被 CCF 的数据狠狠敲打后，题目中的 C 国又接连遭受了几场除了那题中提到的大地震之外的自然灾害，现在你又被 C 国请来解决道路修复的问题，这次你会赢吗？

C 国有 $n$ 座城市，$n-1$ 条双向道路，并且任意两个城市之间可以互相到达。 在 C 国发生了多次自然灾害，每次自然灾害的描述方式如下： - 给出两个城市 $u,v$ 满足 $u \neq v$，对于一个城市 $x$，我们称其在灾害范围内当且仅当从 $u$ 到 $x$ 的简单路径上存在 $v$。 每次自然灾害过后，所有两端点都是在灾害范围内的点的道路将被摧毁，C 国会拨款重新修建道路，使各个城市仍然连通。 但由于技术原因，C 国只能将所有除 $v$ 以外在灾害范围内的城市向 $v$ 修建一条道路。道路长度为此次灾害前这座城市到 $v$ 的简单路径上所有道路的长度之和。 在多次灾害之间，C 国总统想要知道从特定城市 $s$ 出发，到达其他城市的简单路径上所有道路的长度之和的**最大值**。

第一行一个整数 $n$，表示城市的数量。 接下来 $n-1$ 行，每行包括三个用空格隔开的整数 $a,b,l$，表示存在一条连接 $a,b$，长度为 $l$ 的双向道路。 接下来一行一个整数 $q$，表示发生事件的数量。 接下来 $q$ 行，每行首先包含一个整数 $op$。若 $op=1$，接下来两个用空格隔开的整数 $u,v$（保证 $u \neq v$，含义见题目描述），表示一次自然灾害；若 $op=2$，接下来一个整数 $s$（含义见题目描述），表示一次 C 国总统的询问，询问某个特定城市 $s$ 到达其他城市所需要经过的距离中，最长的距离。

对于每次 C 国总统的询问，输出一行一个整数表示答案。

### 【样例解释 1】 对于第一组样例： 对于询问 $1$，此时的道路结构如下：  此时从城市 $5$ 出发到达其他城市所需要经过的距离中，到城市 $4$ 的距离最长，长度为 $9$。 对于询问 $3$、$4$，此时的道路结构如下：  从城市 $1$ 出发到达其他城市所需要经过的距离中，到城市 $4$ 的距离最长，长度为 $6$。 从城市 $3$ 出发到达其他城市所需要经过的距离中，到城市 $4$ 的距离最长，长度为 $7$。 ### 【数据范围】 | 测试点编号 | $n,q\le $ | $l\lt $ | 特殊性质 | | :-: | :-: | :-: | :-: | | $1,2$ | $10^3$ | $10^5$ | 无 | | $3,4$ | $5 \times 10^5$ | $10^9$ | A | | $5,6$ | $5 \times 10^5$ | $10^9$ | B | | $7,8$ | $5 \times 10^5$ | $10^9$ | C | | $9,10$ | $5 \times 10^5$ | $10^9$ | 无 | 特殊性质 A：保证 $op=2$。 特殊性质 B：保证存在 $1 \le pos \le q$，使得 $\forall i \le pos$，第 $i$ 个事件的 $op=1$，$\forall i \gt pos$，第 $i$ 个事件的 $op=2$。 特殊性质 C：若 $op=1$，则 $u=1$。 对于 $100\%$ 的数据，$1 \le n,q \le 5 \times 10^5$，$1 \le a,b,u,v,s \le n$，$u \neq v$，$0 \le l \lt 10^9$，$op \in \{1,2\}$。