P6845 [CEOI 2019] Dynamic Diameter

There is a tree with $n$ nodes, and the edges are weighted. There will be $q$ modifications. Each modification changes the weight of one edge in the tree. After each modification, you need to output the sum of edge weights on the diameter of the tree. **This problem is strictly online.**

The first line contains three integers $n, q, w$, representing the number of nodes, the number of queries, and the upper bound of edge weights. The next $n - 1$ lines each contain three integers $a_i, b_i, c_i$, meaning there is an edge between $a_i$ and $b_i$ with weight $c_i$. The next $q$ lines each contain two encrypted integers $d_j, e_j$. The decryption method is: - $d_j'=(d_j+\text{last})\bmod(n-1)$ - $e_j'=(e_j+\text{last})\bmod w$ Here, $\text{last}$ is the answer to the previous query, with initial value $0$. This means: change the weight of the $(d_j' + 1)$-th edge to $e_j'$.

Output $q$ lines. Each line contains one integer. The integer on the $i$-th line is the total weight on the diameter after the $i$-th modification.

#### Explanation of Sample 1 The decrypted modifications are: ``` 2 1030 0 1050 2 970 ``` The following figure shows how the edge weights in the tree change. The red edge represents the diameter of the tree:  #### Constraints For $100\%$ of the testdata, it is guaranteed that $2 \le n \le 10^5$, $1 \le q \le 10^5$, $1 \le w \le 2\times 10^{13}$, $1 \le a_i, b_i \le n$, $0 \le c_i, e_j < w$, and $0 \le d_j < n - 1$. The detailed subtask constraints and scores are shown in the table below: | Subtask ID | Constraints | Score | | :-: |:-:|:-:| | 1 | $n, q \le 100$ and $w \le 10^4$ | $11$ | | 2 | $n, q \le 5\times 10^3$ and $w \le 10^4$ | $13$ | | 3 | $w \le 10^4$ and all edges are of the form $(1, i)$ | $7$ | | 4 | $w \le 10^4$ and all edges are of the form $(i, 2\times i)$ or $(i, 2\times i + 1)$ | $18$ | | 5 | It is guaranteed that there exists a diameter that passes through node $1$ | $24$ | | 6 | No special constraints | $27$ | #### Notes This problem is translated from [Central-European Olympiad in Informatics 2019](https://ceoi.sk/) [Day 1](https://ceoi.sk/tasks/) [T2 Dynamic Diameter](https://ceoi.sk/static/statements/diameter-ENG.pdf)。 Translated by ChatGPT 5