#1214. czq的贸易帝国

czq的贸易帝国由$n$个省份组成，它们由$n-1$条无向商路互相直接或间接地联通，商路有权值$w_{ij}$。

初始时，czq的贸易本埠$k$在1号省份，每个省份的贸易价值$x_i$均为0。在接下来$q$月，每月都会发生一种事件：

1 x y：czq在$x$号省份种田，使得它的贸易价值增加了$y$。

2 x：czq把他的贸易本埠迁移到了$x$号省份。

czq的商人们会把所有省份的贸易价值导向他的贸易本埠，对于第$i$号省份，导入贸易本埠的贸易价值$p_i=x_i \times w_{kj}$，其中$k$是贸易本埠，$j$为与贸易本埠直接相连且离$i$最近（距其边数最小）的那个省份。特别的，贸易本埠自身的贸易价值不计入导入价值。

现在，czq想问你，每个月他贸易本埠导入的贸易价值。

提示：本题标解的复杂度为严格的$O((n+q)logn)$。

第一行一个整数$n$，为省份个数。

接下来$n-1$行，每行三个整数$u,v,w$，为一条商路。

接下来一行一个整数$q$，为事件个数。

接下来$q$行，每行一个事件，格式如上所述。

对于每个事件，输出一行一个整数，为导入的贸易价值。

样例输入

6
1 2 1
2 3 2
3 4 4
2 5 8
5 6 16
5
1 1 1
1 3 2
2 2
1 5 4
2 6

样例输出

0
2
5
37
112

$1 \leq n,q \leq 10^6$

$1 \leq x \leq n$

$1 \leq y \leq 10^5$

时限5s，输入输出量较大，建议选择较快的方式。