#P3589. 动态树
动态树
动态树
题目描述
给定一棵以结点 为根的树。每个结点最初没有果子。需要处理两种事件:
- 事件 :给一个结点的整棵子树增加果子,子树中的每个结点增加相同数量。
- 事件 :给出若干条树枝,求所有树枝上结点的果子总数。每条树枝是一段祖先到后代的路径,包含两个端点。出现在多条树枝上的结点只计一次。
输入格式
第一行一个整数 ,表示结点数。接下来 行,每行两个整数 ,表示结点 与 之间有一条边。结点编号为 至 。
接下来一行一个整数 ,表示事件数。其后 行,每行是以下一种格式:
- (事件 ):以 为根的子树中,每个结点增加 个果子。
- (事件 ):查询这些路径覆盖的所有结点的果子总数。每一对端点中,一个是另一个的祖先(可以相同),输入顺序不限。
输出格式
对每个事件 ,输出一行一个整数,表示其果子总数对 取模的非负余数。
样例
5
1 2
2 3
2 4
1 5
3
0 1 1
0 2 3
1 2 3 1 1 4
13
数据范围
,。原题说明正式测试的询问使用 ;样例用于说明较少树枝时的同一查询格式。
原测试生成一条树枝时,先选一个结点,再在从该结点到根的路径上选另一个结点。这两个结点就是树枝的端点。
题目来源
By 佚名提供