题目描述
译自 CEOI 2019 Day1 T2「Dynamic Diameter」
你有一个 n 个节点的树,每条边有边权,有 q 次更新,每次修改一条边的边权,并询问树的直径。
本题强制在线。
输入格式
第一行输入三个正整数 n,q,w,表示节点数,询问数,以及一条边权值的上限。
接下来 n−1 行,其中第 i 行三个整数 ai,bi,ci(1≤ai,bi≤n,0≤ci<w),表示链接节点 ai,bi 的一条边权值为 ci。
接下来 q 行,每行两个整数 d,e(0≤d<n−1,0≤e<w),表示加密前的数据。
记 last 为上次询问的答案,第一次时为 0。解密后的数据为 d′=(d+last)mod(n−1)+1,e′=(e+last)modw。表示将第 d′ 条边的权值修改为 e′。
输出格式
输出 q 行,每行一个整数,表示修改后的直径。
样例 1
4 3 2000
1 2 100
2 3 1000
2 4 1000
2 1030
1 1020
1 890
2030
2080
2050
这组样例如下图所示:
最左端图片是这棵树的初始状态,接下来的每张图表示在更新之后的情况。更改后的边权用绿色标记,直径用红色标记。
第一个询问更改了第三条边的边权,即 {2,4} 的边权改为 1030。两点间最大距离为 2030,即 3 到 4 的距离。
因为第一个询问的答案为 2030,第二个询问为:
d2′=(1+2030)mod3=0e2′=(1020+2030)mod2000=1050
因此边 {1,2} 的边权改为 1050,这使得从 1 到 4 的距离最大,距离为 2080。
第三个询问为:
d3′=(1+2080)mod3=2e3′=(890+2080)mod2000=970
因此边 {2,4} 的边权改为 970,这使得从 1 到 3 的距离最大,距离为 2050。
10 10 10000
1 9 1241
5 6 1630
10 5 1630
2 6 853
10 1 511
5 3 760
8 3 1076
4 10 1483
7 10 40
8 2051
5 6294
5 4168
7 1861
0 5244
6 5156
3 3001
8 5267
5 3102
8 3623
6164
7812
8385
6737
6738
7205
6641
7062
6581
5155
数据范围与提示
对于 100% 的数据,保证 2≤n≤105,1≤q≤105,1≤w≤2×1013。
子任务编号 |
n,q |
w |
特殊限制 |
分值 |
1 |
≤102 |
≤104 |
|
11 |
2 |
≤5×103 |
13 |
3 |
≤105 |
边的形式都为 (1,i) |
7 |
4 |
边的形式都为 (i,2i) 或 (i,2i+1) |
18 |
5 |
≤2×1013 |
保证有一条直径经过 1 号节点 |
24 |
6 |
|
27 |