ZY的核电站 (nuclear.in/out/cpp)

时间限制: 5 s / 内存限制: 256 MB / 打开O2优化

题目描述

“ZY喜欢玩核电站。”

ZY的核电站非常特殊。早在2038年，ZY就发现了高分子有机物的完全裂解可以释放大量的核能的原理（这句话纯属FP）。因此ZY的核电站反应堆里面全是高分子有机物，可惜只有一个。
为了使发电量尽可能大，ZY找到了一种能使有机物完全裂解的方式，使释放出来的能量最大。由于这是ZY的有机物，因此裂解方式也非常奇葩。下面是ZY在2039年的论文《论ZY对MC¹核电站的巨大贡献》中的节选片段：

......
我们的有机物是由$n$个各种原子构成的，原子之间通过不同的共价键相连。

($\text{H}$太多了，到时候这些没用的氢原子都会被ZY丢掉)
......
为了方便进行裂解，这个有机物是没有环的，这样就可以节约成本来买**V*P***......
......
每次裂解都会断开一个共价键，此时这个有机物会分为两部分。并且释放大量的能量......
设放出的能量为$E$，有机物裂解后的两部分的共价键的集合分别为$A$和$B$，则：、
$$ E = \sum_{a\in A} a.\text{energy} \cdot \sum_{b\in B} b.\text{energy} \tag{ZY's energy theorem}$$

其中$\text{energy}$表示共价键的能量。
......
为了充分利用有机物中的能量，每裂解一个共价键后，我们有办法无损耗无成本的将其还原，即有机物会变得和裂解前一样。但是出于种种原因，这个共价键就不能再次进行裂解了。除非ZY发出SB之神力来使所有的共价键复活......
......
那么，一个有机物完全裂解所能放出的能量为所有共价键裂解一次后所放出的能量之和。
......

(实际上，ZY的这篇论文长达$2147483647$字)

当然，ZY的智商理论上为$-\infty$。因此它的核电站其实非常辣鸡。反应堆中的有机物不一定是稳定的，但是ZY利用LCT算法以$O(\infty!)$的时间复杂度内成功地保证了有机物的结构，这样就方便ZY发出SB之神力。但是令ZY想跳楼的是，总有一个共价键的能量在维护有机物结构时会变动。然而”机智”的ZY可以发现这些变化。
ZY只希望能够快速算出当前的有机物通过完全裂解究竟能放出多少能量。由于ZY的数学只有学前班水平，所以每当她算到一半时，这个有机物又开始乱搞了，ZY就只能用LCT来重新维护它。
一年之内，ZY的核电站什么电都没有发。为了快速计算，ZY找到了你这个**。
ZY希望你能给出一个好方法来帮助她计算当前有机物完全裂解能放出的能量。

输入格式

第$1$行输入两个正整数$n$，$m$。$n$表示有机物中原子的数量，$m$表示ZY维护有机物结构的次数。
接下来$n - 1$行描述一个有机物。对于每一行输入三个整数$u$，$v$和$e$，表示第$u$号原子和第$v$号原子之间以能量为$e$的共价键相连。
接下来$m$行，每一行描述一个共价键的键能变化。每行输入三个整数$u$，$v$和$e$，表示第$u$号原子和第$v$号原子之间的共价键的能量变为$e$。保证第$u$号原子和第$v$号原子之间存在共价键。

输出格式

对于每次共价键能量的变动，输出一行一个整数，表示键能改变后的有机物完全裂解能放出的能量。

输入样例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

1 2 2
1 2 3
2 3 3
1 2 0

输出样例

1
2
3
4

13
15
16
10

数据范围及提示

对于第一个询问:
裂解$1$和$2$之间的共价键: $1 \times (2 + 1 + 1 + 1) = 5$
裂解$2$和$3$之间的共价键: $(2 + 1 + 1) \times (1 + 1) = 8$
其余的共价键裂解得到的能量均为$0$。
因此答案为$13$。

对于$10\%$的数据: $n \le 1,000, \; m \le 5,000$
对于$10\%$的数据: $n \le 10,000, \; m \le 500,000$
对于$10\%$的数据: $n \le 100,000, \; m \le 100$
对于$10\%$的数据: $n \le 10,000, \; m \le 1,000,000$
对于另外$20\%$的数据: 有机物没有支链。
对于$100\%$的数据: $n \le 200,000, \; m \le 1,000,000, \; e \le 10 $