时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
我们给定两棵
带权树 
与

,大小均为

,定义点
&preview=true)
的距离为
%2Bdep_2(x)%2Bdep_2(y)&preview=true)
;
即两者在树

上的距离加上两者在树

上的深度(我们认为树

的根为

,同时深度定义为此点到根节点的路径的边权和)。你需要找到两个点并最大化两者间距离,支持修改树

上的边权。注意每次修改的点和

都是随机生成的。
注意,你找到的两个点

应满足
ps:我们保证树 T2 的生成方式为,对于所有点 i >= 2,其父亲为 [1, i-1] 中随机的一个点。
输入描述:
第一行三个正整数

,其中

表示树

与

的大小,

表示变换次数。
接下来

行描述树

,其中每行三个正整数

表示一条

的无向边,其边权为

接下来

行描述树

,其中每行三个正整数

表示一条

的无向边,其边权为

接下来

行,每行两个正整数

,表示树

中

到

的父亲的边的边权增大了

,请注意树

的根为

,保证

输出描述:
共

行,第一行一个正整数表示树

没有变换时的答案。
接下来

行每行一个正整数第

次变换后的答案。
示例1
输入
复制
3 0
1 2 1
2 3 4
1 2 1
2 3 4
示例2
输入
复制
10 5
2 1 9169934
3 2 9139781
4 3 8204914
5 4 4022253
6 5 4461495
7 6 5451751
8 7 9161101
9 8 9325703
10 9 1755549
2 1 428512
3 2 3226094
4 3 4200469
5 3 7814858
6 4 8688657
7 2 5533607
8 5 1461632
9 5 9970292
10 5 8700469
10 183804036
6 238058020
3 576677263
5 898699625
7 522470322
输出
复制
80862414
264666450
484269825
1637624351
3196352808
3196352808
备注:
,输入数据保证树
以及每次修改的端点随机生成。保证
,保证
,且 k > 0,保证