#P10371. [2021年联测]树
[2021年联测]树
题目描述
给定一棵有 个节点的无向树,节点编号 ,点权初始均为 。另给定由 条树上简单路径组成的序列。路径由两个端点确定,并包含这两个端点。
有三种操作。
1 u v k:将从 到 的路径上的每个节点的点权加上 。2 x u v:将序列中第 条路径替换为从 到 的路径。3 l r:求序列中第 到第 条路径的点权和之和。同一个节点若出现在多条被查询的路径中,在每条路径中各计一次。
输入格式
第一行三个整数 。接下来 行,每行两个整数 ,表示树上的一条边。接下来 行,第 行两个整数 ,表示第 条初始路径。
再接下来 行,每行给出一次操作,格式见上。
输出格式
每次操作 3 输出一行一个整数,表示对应答案对 取模的结果。
样例
5 3 6
1 2
1 3
3 4
3 5
2 3
1 4
4 5
1 1 3 1
3 1 3
2 3 2 5
3 2 3
1 4 5 2
3 1 2
5
4
10
数据范围
。所有节点及路径编号合法。本站评测内存限制为 MB。
| 子任务 | 分值 | 上界 | 特殊性质 |
|---|---|---|---|
| 1 | 5 | 500 | |
| 2 | 10 | 8000 | |
| 3 | 20 | A、B | |
| 4 | A | ||
| 5 | B | ||
| 6 | 15 | ||
| 7 | 10 |
性质 A:对于所有 ,树中有连接 与 的边。性质 B:没有操作 2。