#P3589. 动态树

    ID: 2790 传统题 2000ms 512MiB 尝试: 924 已通过: 226 难度: 6 上传者: 标签>难度分类提高树算法树链剖分子树转区间贪心区间合并数据结构懒标记线段树CF2000树论

动态树

动态树

题目描述

给定一棵以结点 11 为根的树。每个结点最初没有果子。需要处理两种事件:

  • 事件 00:给一个结点的整棵子树增加果子,子树中的每个结点增加相同数量。
  • 事件 11:给出若干条树枝,求所有树枝上结点的果子总数。每条树枝是一段祖先到后代的路径,包含两个端点。出现在多条树枝上的结点只计一次。

输入格式

第一行一个整数 nn,表示结点数。接下来 n−1n-1 行,每行两个整数 u,vu,v,表示结点 uu 与 vv 之间有一条边。结点编号为 11 至 nn。

接下来一行一个整数 qq,表示事件数。其后 qq 行,每行是以下一种格式:

  • (事件 00)0 u δ0\ u\ \delta:以 uu 为根的子树中,每个结点增加 δ\delta 个果子。
  • (事件 11)1 k u1 v1 … uk vk1\ k\ u_1\ v_1\ \ldots\ u_k\ v_k:查询这些路径覆盖的所有结点的果子总数。每一对端点中,一个是另一个的祖先(可以相同),输入顺序不限。

输出格式

对每个事件 11,输出一行一个整数,表示其果子总数对 2312^{31} 取模的非负余数。

样例

5
1 2
2 3
2 4
1 5
3
0 1 1
0 2 3
1 2 3 1 1 4
13

数据范围

1≤n,q≤2×1051\le n,q\le2\times10^5,1≤k≤51\le k\le5。原题说明正式测试的询问使用 k=5k=5;样例用于说明较少树枝时的同一查询格式。

原测试生成一条树枝时,先选一个结点,再在从该结点到根的路径上选另一个结点。这两个结点就是树枝的端点。

题目来源

By 佚名提供