小 Z 有一棵 $ n $ 个节点构成的树,这棵树以点 $ 1 $ 为根,边权均为 $ 1 $ ,每个节点 $ x $ 有点权 $ a_x $ ,初始所有节点的权值为 $ 0 $ .
小 Z 想对这棵树进行总共 $ m $ 次操作,并且 小 Z 希望能够支持以下四种类型的操作:
- 给定 $ x,y,k,v $ ,对满足节点 $ i $ 到树上唯一的最短路径 $ (x,y) $ 的最短距离 $ \leq k $ 的所有节点 $ i $ 的权值增加 $ v $ ,即 $ a_i \leftarrow a_i+v $ .
- 给定 $ x,v $ ,将点 $ x $ 的子树内的所有节点 $ i $ 的权值增加 $ v $ ,即 $ a_i \leftarrow a_i+v $ .
- 给定 $ x,y,k $ ,查询所有满足节点 $ i $ 到树上唯一的最短路径 $ (x,y) $ 的最短距离 $ \leq k $ 的所有节点 $ i $ 的权值的和.
- 给定 $ x $ ,查询点 $ x $ 的子树内的所有节点 $ i $ 的权值和.
由于答案会比较大,输出对 $ 2^{64} $ 取模即可.
输入格式
第一行为两个正整数 $ n,m $ .
接下来第 $ 2 $ 行到第 $ n $ 行每行两个正整数 $ u,v $ 来描述树上的一条边.
接下来 $ m $ 行,每行先给出一个操作类型 $ op $ .
当 $ op=1 $ 时给定 $ x,y,k,v $ 来描述操作一;
当 $ op=2 $ 时给定 $ x,v $ 来描述操作二;
当 $ op=3 $ 时给定 $ x,y,k $ 来描述操作三;
当 $ op=4 $ 时给定 $ x $ 来描述操作四.
输出格式
对于每个操作 $ 3 $ 和操作 $ 4 $ ,输出其对应的答案对 $ 2^{64} $ 取模的结果.
数据范围
数据范围: $ 1 \leq n,m \leq 2 \times 10^5 , 1 \leq x,y \leq n , 1 \leq v \leq 10^9 ,0 \leq k \leq 3 $ .
时间限制 7s ,空间限制 1G .
部分分
数据范围: $ 1 \leq n,m \leq 2 \times 10^5 , 1 \leq x,y \leq n , 1 \leq v \leq 10^9 ,0 \leq k \leq 3 $ .
子任务 1 (10分) : $ 1 \leq n , m \leq 5 \times 10^3 $ .
子任务 2 (10分) : $ k=0 $ .
子任务 3 (5分) : 保证树形态构成一条形如 $ 1 $ 连接 $ 2 $ 连接 $ ... $ 连接 $ n $ 的链(所有边均可以表示为 $ i $ 连接 $ i+1 $ 的形式).
子任务 4 (10分) : 保证 $ k=1 $ ,操作类型只包含操作一和操作三,并且操作一和操作三满足 $ x=y $ ,即修改和查询的链是单点.
子任务 5 (10分) : 保证操作类型只包含操作一和操作三,并且操作一和操作三满足 $ x=y $ ,即修改和查询的链是单点.
子任务 6 (15分) : 保证操作一和操作三满足 $ x=y $ ,即修改和查询的链是单点.
子任务 7 (15分) : $ k \leq 1 $ .
子任务 8 (25分) : 无特殊限制.