当前没有测试数据。

题目描述

有一棵树，含 $n$ 个节点，边带权。

会有 $q$ 次修改，每次会将树上的一条边的边权进行修改，在每次修改后，您需要求出每次修改后，这棵树的直径上的边权和。

本题强制在线。

输入格式

第一行为三个整数 $n,q,w$，分别表示点的个数，询问的个数和边权的上限。

接下来 $n-1$ 行，每一行为三个整数 $a_i,b_i,c_i$，表示 $a_i$ 到 $b_i$ 有一条边权为 $c_i$ 的边。

接下来 $q$ 行，每行两个经过加密的整数 $d_j,e_j$。

解密方式如下：

• $d_j'=(d_j+\text{last})\bmod(n-1)$
• $e_j'=(e_j+\text{last})\bmod w$

其中 $\text{last}$ 表示上一个询问的答案，初值为 $0$。

表示将第 $d_j'+1$ 条边的边权改为 $e_j'$。

输出格式

共输出 $q$ 行，一行一个整数，第 $i$ 行的整数表示在第 $i$ 次修改后的直径上的权值总和。

样例 #1

样例输入 #1

4 3 2000
1 2 100
2 3 1000
2 4 1000
2 1030
1 1020
1 890

样例输出 #1

2030
2080
2050

样例 #2

样例输入 #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 解释

解密后的修改如下：

2 1030
0 1050
2 970

如图为树的边权变化过程，红边代表树的直径：

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据，保证 $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$，$0\le d_j<n-1$。

详细子任务限制及分值如下表：

子任务编号	限制	分值
1	$n,q\le 100$ 且 $w\le 10^4$	$11$
2	$n,q\le 5\times 10^3$ 且 $w\le 10^4$	$13$
3	$w\le 10^4$ 且边的形式均为 $(1,i)$	$7$
4	$w\le 10^4$ 且边的形式均为 $(i,2\times i)$ 或 $(i,2\times i+1)$	$18$
5	保证有一条直径经过 $1$ 号节点	$24$
6	无特殊限制	$27$