坐标
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

我们给定两棵带权树 ,大小均为 ,定义点 的距离为

即两者在树 上的距离加上两者在树 上的深度(我们认为树 的根为 ,同时深度定义为此点到根节点的路径的边权和)。你需要找到两个点并最大化两者间距离,支持修改树 上的边权。注意每次修改的点和都是随机生成的。

注意,你找到的两个点  应满足  

ps:我们保证树 T2 的生成方式为,对于所有点 i >= 2,其父亲为 [1, i-1] 中随机的一个点。

输入描述:

第一行三个正整数 ,其中 表示树 T_1T_2 的大小, 表示变换次数。
接下来 行描述树 ,其中每行三个正整数 表示一条 的无向边,其边权为
接下来 行描述树 ,其中每行三个正整数 表示一条 的无向边,其边权为
接下来 行,每行两个正整数 ,表示树 的父亲的边的边权增大了 ,请注意树 的根为 ,保证

输出描述:

行,第一行一个正整数表示树 没有变换时的答案。

接下来 行每行一个正整数第 次变换后的答案。
示例1

输入

复制
3 0
1 2 1
2 3 4
1 2 1
2 3 4

输出

复制
10
示例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,保证