给您一个 $$$n$$$ 顶点上的加权无向树和 $$$q$$$ 更新列表。每次更新都会更改一条边的权重。任务是在每次更新后输出树的直径。
(两个顶点之间的距离是连接它们的唯一简单路径上的权重之和。直径是所有这些距离中最大的。)
输入
第一行包含三个空格分隔的整数 $$$n$$$、$$$q$$$ 和 $$$w$$$ ($$$2 \leq n \leq 100,000, 1 \leq q \leq 100,000$$$, $$$1 \leq w \leq 20,000,000,000,000$$$) – 树中的顶点数、更新次数以及边权重的限制。顶点编号为 $$$1$$$ 到 $$$n$$$。
接下来是描述初始树的 $$$n-1$$$ 行。这些行的第 $$$i$$$ 包含三个空格分隔的整数 $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$0 \leq c_i < w$$$) 意味着最初,顶点 $$$a_i$$$ 和$$$b_i$$$ 重量为 $$$c_i$$$。保证这些 $$$n-1$$$ 行描述一棵树。
最后,后面是描述查询的 $$$q$$$ 行。这些行的第 $$$j$$$ 包含两个空格分隔的整数 $$$d_j$$$, $$$e_j$$$ ($$$0 \leq d_j < n - 1, 0 \leq e_j < w$$$)。然后根据以下方案转换这两个整数:
- $$$d'_j = (d_j + 最后) \bmod (n - 1)$$$
- $$$e'_j = (e_j + 最后) \bmod w$$$
输出
输出 $$$q$$$ 行。对于每个 $$$i$$$,$$$i$$$ 行应包含第 $$$i$$$ 次更新后树的直径。
示例
输入 #1
4 3 2000 1 2 100 2 3 1000 2 4 1000 2 1030 1 1020 1 890
输出 #1
2030 2080 2050
输入 #2
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
输出 #2
6164 7812 8385 6737 6738 7205 6641 7062 6581 5155
注意
评分:
子任务 1(11 分):$$$n,q \leq 100$$$ 和 $$$w \leq 10,000$$$
子任务 2(13 分):$$$n,q \leq 5,000$$$ 和 $$$w \leq 10,000$$$
子任务 3(7 分):$$$w \leq 10,000$$$ 并且树的边恰好是 $$$\{1, i\}$$$ 形式的所有有效边(因此,树是以顶点 1 为中心的星形。)
子任务 4(18 分):$$$w \leq 10,000$$$,并且树的边恰好是 $$$\{i, 2i\}$$$ 和 $$$\{i, 2i+1\}$$$ 形式的所有有效边(因此,如果我们在顶点 1 处建立树的根,它将是平衡二叉树。)
子任务5(24分):保证每次更新后最长的简单路径经过顶点$$$1$$$
子任务6(27分):无额外限制
第一个示例如下图所示。最左边的图片显示了图表的初始状态。下面的每张图片都描述了更新后的情况。更新后的边的权重涂成绿色,直径涂成红色。
第一个查询将 $$$3$$$rd 边的权重(即 $$$\{2, 4\}$$$ 更改为 $$$1030$$$。任何一对顶点之间的最大距离是 $$$2030$$$ – $$$3$$$ 和 $$$4$$$ 之间的距离。
由于答案是 $$$2030$$$,第二个查询是 $$$$$$d'_2 = (1 + 2030) \bmod 3 = 0$$$$$$ $$$$$$e'_2 = (1020 + 2030) \bmod 2000 = 1050$$$$$$ 因此边的权重$$$\{1, 2\}$$$ 更改为 $$$1050$$$。这使得 $$$\{1, 4\}$$$ 成为距离最大的对,即 $$$2080$$$。
第三个查询被解码为 $$$$$$d'_3 = (1 + 2080) \bmod 3 = 2$$$$$$ $$$$$$e'_3 = (890 + 2080) \bmod 2000 = 970$$$$$$ 随着边权重 $$$\{2, 4\}$$$ 减小到$$$970$$$,最远的一对突然变成$$$\{1, 3\}$$$ 和$$$2050$$$。