CF1192B.Dynamic Diameter

You are given a weighted undirected tree on $n$ vertices and a list of $q$ updates. Each update changes the weight of one edge. The task is to output the diameter of the tree after each update.

(The distance between two vertices is the sum of the weights on the unique simple path that connects them. The diameter is the largest of all those distances.)

给你一棵包含 $n$ 个顶点的带权无向树，以及一个包含 $q$ 次更新的操作列表。每次更新会修改某条边的权重。你的任务是在每次更新后输出该树的直径。

（两个顶点之间的距离定义为连接它们的唯一简单路径上所有边的权重之和；树的直径即为所有顶点对之间距离的最大值。）

The first line contains three space-separated integers $n$, $q$ and $w$ ($2 \leq n \leq 100,000, 1 \leq q \leq 100,000$, $1 \leq w \leq 20,000,000,000,000$) – the number of vertices in the tree, the number of updates and the limit on the weights of edges. The vertices are numbered $1$ through $n$.

Next, $n-1$ lines describing the initial tree follow. The $i$-th of these lines contains three space-separated integers $a_i$, $b_i$, $c_i$ ($1 \leq a_i, b_i \leq n$, $0 \leq c_i \lt w$) meaning that initially, there is an edge between vertices $a_i$ and $b_i$ with weight $c_i$. It is guaranteed that these $n-1$ lines describe a tree.

Finally, $q$ lines describing queries follow. The $j$-th of these lines contains two space-separated integers $d_j$, $e_j$ ($0 \leq d_j \lt n - 1, 0 \leq e_j \lt w$). These two integers are then transformed according to the following scheme:

• $d'_j = (d_j + last) \bmod (n - 1)$
• $e'_j = (e_j + last) \bmod w$

where $last$ is the result of the last query (initially $last=0$). Tuple $(d'_j, e'_j)$ represents a query which takes the $d'_j+1$-th edge from the input and sets its weight to $e'_j$.

第一行包含三个以空格分隔的整数 $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 \lt w$），表示初始时顶点 $a_i$ 与 $b_i$ 之间存在一条权重为 $c_i$ 的边。保证这 $n-1$ 行所描述的是一棵树。

最后是 $q$ 行，每行描述一个查询。其中第 $j$ 行包含两个以空格分隔的整数 $d_j$、$e_j$（$0 \leq d_j \lt n - 1$，$0 \leq e_j \lt w$）。这两个整数将按如下规则进行变换：

• $d'_j = (d_j + last) \bmod (n - 1)$
• $e'_j = (e_j + last) \bmod w$

其中 $last$ 是上一次查询的结果（初始时 $last = 0$）。元组 $(d'_j, e'_j)$ 表示一个查询：将输入中第 $d'_j+1$ 条边的权重修改为 $e'_j$。

Output $q$ lines. For each $i$, line $i$ should contain the diameter of the tree after the $i$-th update.

输出 $q$ 行。对于每个 $i$，第 $i$ 行应包含第 $i$ 次更新后的树的直径。

The first sample is depicted in the figure below. The left-most picture shows the initial state of the graph. Each following picture depicts the situation after an update. The weight of the updated edge is painted green, and the diameter is red.

The first query changes the weight of the $3$rd edge, i.e. ${2, 4}$, to $1030$. The largest distance between any pair of vertices is $2030$ – the distance between $3$ and $4$.

As the answer is $2030$, the second query is $$d'_2 = (1 + 2030) \bmod 3 = 0$$ $$e'_2 = (1020 + 2030) \bmod 2000 = 1050$$ Hence the weight of the edge ${1, 2}$ is changed to $1050$. This causes the pair ${1, 4}$ to be the pair with the greatest distance, namely $2080$.

The third query is decoded as $$d'_3 = (1 + 2080) \bmod 3 = 2$$ $$e'_3 = (890 + 2080) \bmod 2000 = 970$$ As the weight of the edge ${2, 4}$ decreases to $970$, the most distant pair is suddenly ${1, 3}$ with $2050$.

第一个样例如下图所示。最左侧的图片展示了图的初始状态，随后每张图片展示一次更新后的状态。被更新的边的权重以绿色标出，图的直径以红色标出。

第一个查询将第 $3$ 条边（即边 $\{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$。