You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小龙的邻居家有一颗苹果树$T_1$, 小龙自己家也有一颗苹果树$T_2$.

这两颗苹果树是真正意义的树, 他们是具有$n$个点, $n-1$条带权值边的联通无向图. 节点编号从$1$到$n$.

并且小龙家的苹果树$T_2$的根节点已经确定是$1$号节点. $T_1$和$T_2$都有$n$个节点.

对于$n$个节点中的任意不同的两个节点$x$和$y$, 小龙发明了"苹果距离", $(x, y)$的苹果距离定义如下:

首先在$1$到$n$号节点中, 找到两个节点$x$和$y$($x$和$y$不可以相同), 然后苹果距离定义为$x$和$y$在$T_1$上的距离加上$x$和$y$在$T_2$上的深度($T_2$的根为$1$),

数学公式为

其中 $\operatorname{dist}_{1}(x, y)$ 为 $x, y$ 在苹果树 $T_{1}$ 上的距离， $\operatorname{dep}_{2}(x)$ 表示点 $x$ 在苹果树 $T_{2}$ 上到 $1$ 号节点的距离(即树 $T_{2}$ 以$1$为根后, $x$号节点的深度 ，请注意树有边权)

特别的, 小龙定义了相同顶点之间的苹果距离为$0$.

小龙想要让你帮他找出苹果距离最大的两个顶点, 输出他们的最大苹果距离.

小龙为了体现他是$T_2$这颗苹果树的主人, 他还会让$T_2$苹果树上的边权随机增大 $m$ 次, 并且边权增大的效果是累计的, 之前增大的效果会对后续均产生影响.

你需要求出每次变换后最大的苹果距离.

输入格式

第一行两个整数 $n, m$ ，其中 $n$ 表示树 $T_{1}$ 与 $T_{2}$ 的大小， $m$ 表示变换次数。

接下来 $n-1$ 行描述树 $T_{1}$ ，其中每行三个正整数 $x, y, z$ 表示一条 $x$ 和$y$ 的无向边，其边权为 $z$

接下来 $n-1$ 行描述树 $T_{2}$ ，其中每行三个正整数 $x, y, z$ 表示一条 $x$和$y$ 的无向边，其边权为 $z$

接下来 $m$ 行，每行两个正整数 $x, k$ ，表示树 $T_{2}$ 中 $x$ 到 $x$ 的父亲的边的边权增大了 $k$ ，请注意树 $T_{2}$ 的根为 $1$ ，保证 $x \neq 1$

输出格式

共 $m+1$ 行，第一行一个整数表示树 $T_{2}$ 没有变换时的答案。

接下来 $m$ 行每行一个整数表示第 $i$ 次变换后的答案。

样例 #1

样例输入 #1

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

样例输出 #1

10

样例 #2

样例输入 #2

3 2
1 2 1
2 3 4
1 2 1
2 3 4
2 10
3 10

样例输出 #2

10
30
40

样例 #3/#4/#5/#6/#7

见下发文件中ex_apple3/4/5/6/7.in/out

ex_apple5对应$T_2$除$1$外父亲均为$1$的数据情况

样例解释

对于样例$1$, 选择$1$和$3$的苹果距离, 为$10$, 选择$2$和$3$的苹果距离, 也是$10$

对于样例$2$, 最初选择$1$和$3$或者$2$和$3$的苹果距离均为$10$, 修改后选择$2$和$3$的苹果距离最大, 分别是$30$和$40$

数据范围

• 除特殊说明的$20\%$的数据以外，保证树 $T_{2}$ 为按如下规则随机生成的: 对于属于$2$到$n$的所有节点$i$, 令其父亲为 $[1, i)$ 中的随机数。
• 保证修改操作中的$x$均从$[2, n]$随机生成。

对于 $20 \%$ 的数据，有 $n \leq 3000, m=0$

对于 $40 \%$ 的数据，有 $n \leq 10^{5}, m=0$

对于另 $20 \%$ 的数据，保证 $T_{2}$ 中的除 $1$ 以外的点的父亲均为 $1$, 此部分数据不满足树$T_2$随机生成的性质

对于 $100 \%$ 的数据， 有 $2 \leq n \leq 10^{5}, 0 \leq m \leq 10^{5}, 1 \leq z \leq 2*10^9, 1 \leq k \leq 2*10^9$, 保证给出的$T_1$和$T_2$均为一颗树

其他要求

每个测试点时限：$4$s 内存上限：$512$M