loj#P3163. 「CEOI2019」动态直径
「CEOI2019」动态直径
题目描述
译自 CEOI 2019 Day1 T2「Dynamic Diameter」
你有一个 个节点的树,每条边有边权,有 次更新,每次修改一条边的边权,并询问树的直径。
本题强制在线。
输入格式
第一行输入三个正整数 ,表示节点数,询问数,以及一条边权值的上限。
接下来 行,其中第 行三个整数 ,表示链接节点 的一条边权值为 。
接下来 行,每行两个整数 ,表示加密前的数据。
记 为上次询问的答案,第一次时为 。解密后的数据为 $d' = (d + \mathrm{last}) \bmod (n - 1) + 1, e' = (e + \mathrm{last}) \bmod w$。表示将第 条边的权值修改为 。
输出格式
输出 行,每行一个整数,表示修改后的直径。
4 3 2000
1 2 100
2 3 1000
2 4 1000
2 1030
1 1020
1 890
2030
2080
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
数据范围与提示
对于 的数据,保证 $2\le n \le 10^5, 1\le q\le 10^5, 1\le w \le 2\times 10^{13}$。
子任务编号 | 特殊限制 | 分值 | ||
---|---|---|---|---|
边的形式都为 | ||||
边的形式都为 或 | ||||
保证有一条直径经过 号节点 | ||||