QOJ.ac

QOJ

Time Limit: 7 s Memory Limit: 1024 MB Total points: 100
[+8]

# 7767. 数据结构

Statistics

小 Z 有一棵 n 个节点构成的树,这棵树以点 1 为根,边权均为 1 ,每个节点 x 有点权 ax ,初始所有节点的权值为 0 .

小 Z 想对这棵树进行总共 m 次操作,并且 小 Z 希望能够支持以下四种类型的操作:

  1. 给定 x,y,k,v ,对满足节点 i 到树上唯一的最短路径 (x,y) 的最短距离 k 的所有节点 i 的权值增加 v ,即 aiai+v .
  2. 给定 x,v ,将点 x 的子树内的所有节点 i 的权值增加 v ,即 aiai+v .
  3. 给定 x,y,k ,查询所有满足节点 i 到树上唯一的最短路径 (x,y) 的最短距离 k 的所有节点 i 的权值的和.
  4. 给定 x ,查询点 x 的子树内的所有节点 i 的权值和.

由于答案会比较大,输出对 264 取模即可.

输入格式

第一行为两个正整数 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 ,输出其对应的答案对 264 取模的结果.

数据范围

数据范围: 1n,m2×105,1x,yn,1v109,0k3 .

时间限制 7s ,空间限制 1G .

部分分

数据范围: 1n,m2×105,1x,yn,1v109,0k3 .

子任务 1 (10分) : 1n,m5×103 .

子任务 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分) : k1 .

子任务 8 (25分) : 无特殊限制.