#P10395. [2021年联测]sumsum
[2021年联测]sumsum
题目描述
给定一棵有 个节点的无向树,节点编号为 ,初始点权为 。另给定两个整数 。
每次操作给出 ,先把树上从 到 的唯一路径上的所有点权增加 ,包括两个端点。然后求所有包含 到 个节点的简单路径的权值之和。一条路径的权值是它包含的点权之和。路径不区分方向,单个节点也是一条包含一个节点的路径。
点权更新持续生效。每次操作后,将所求的总和对 取模。
输入格式
第一行四个整数 。第二行 个整数 。
第三行 个整数 ,其中 表示节点 与节点 有一条边。
接下来 行,每行三个整数 ,表示一次操作。
输出格式
输出 行,每行一个整数,表示相应操作后的答案。
样例
10 10 3 6
36 11 76 24 71 89 24 63 75 40
1 1 2 2 3 3 4 4 5
2 5 18
5 7 95
7 10 82
8 2 99
8 1 85
7 7 60
1 5 85
4 3 38
9 4 17
1 1 99
7591
17186
26124
32163
39473
39953
46073
49835
50328
52803
数据范围
,,,。
| 原测试点 | 附加性质 | ||
|---|---|---|---|
| 1 | 10 | ||
| 2 | 50 | ||
| 3 | 300 | ||
| 4 | 2000 | 2000 | |
| 5 | |||
| 6 | |||
| 7 | |||
| 8 | 相同的 至多出现两次 | ||
| 9–10 | |||