背景

你是参加 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 国总统的询问，输出一行一个整数表示答案。

6
1 2 1
1 3 1
1 4 4
2 5 4
2 6 1
4
2 5
1 6 2
2 1
2 3

9
6
7

提示

【样例解释 1】

对于第一组样例：

对于询问 $1$，此时的道路结构如下：

此时从城市 $5$ 出发到达其他城市所需要经过的距离中，到城市 $4$ 的距离最长，长度为 $9$。

对于询问 $3$、$4$，此时的道路结构如下：

从城市 $1$ 出发到达其他城市所需要经过的距离中，到城市 $4$ 的距离最长，长度为 $6$。

从城市 $3$ 出发到达其他城市所需要经过的距离中，到城市 $4$ 的距离最长，长度为 $7$。

【数据范围】

特殊性质 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\}$。