← 返回题目列表

Codeforces · 1192/B

B. 动态直径

中文机器翻译题面 查看原题

给您一个 $$$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$$$。