#P10371. [2021年联测]树

    ID: 9489 传统题 2000ms 40MiB 尝试: 9 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-根号分块虚树树上差分LCAST 表一维前缀和离线查询补充相邻点 LCA栈建虚树贡献法

[2021年联测]树

题目描述

给定一棵有 nn 个节点的无向树,节点编号 1,…,n1,\ldots,n,点权初始均为 00。另给定由 mm 条树上简单路径组成的序列。路径由两个端点确定,并包含这两个端点。

有三种操作。

  • 1 u v k:将从 uu 到 vv 的路径上的每个节点的点权加上 kk。
  • 2 x u v:将序列中第 xx 条路径替换为从 uu 到 vv 的路径。
  • 3 l r:求序列中第 ll 到第 rr 条路径的点权和之和。同一个节点若出现在多条被查询的路径中,在每条路径中各计一次。

输入格式

第一行三个整数 n,m,qn,m,q。接下来 n−1n-1 行,每行两个整数 u,vu,v,表示树上的一条边。接下来 mm 行,第 ii 行两个整数 u,vu,v,表示第 ii 条初始路径。

再接下来 qq 行,每行给出一次操作,格式见上。

输出格式

每次操作 3 输出一行一个整数,表示对应答案对 2322^{32} 取模的结果。

样例

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

数据范围

0≤k<2320\le k<2^{32}。所有节点及路径编号合法。本站评测内存限制为 4040 MB。

子任务 分值 n,m,qn,m,q 上界 特殊性质
1 5 500
2 10 8000
3 20 5×1045\times10^4 A、B
4 A
5 B
6 15
7 10 10510^5

性质 A:对于所有 1≤i<n1\le i<n,树中有连接 ii 与 i+1i+1 的边。性质 B:没有操作 2。

原 PDF 题面