#O1098. 树上路径操作

树上路径操作

题目描述

给定一棵 nn 个结点的树,每个结点有点权 wiw_i。维护 qq 次操作:

  • 1 u v k:把 uu 到 vv 路径上所有结点的点权加上 kk;
  • 2 u v:询问 uu 到 vv 路径上点权之和;
  • 3 x:询问以 xx 为根的子树内点权之和。

输入格式

第一行两个整数 n,qn,q。

第二行 nn 个整数 wiw_i。

接下来 n−1n-1 行,每行两个整数,表示一条边。

接下来 qq 行,每行一个操作。

输出格式

对每个 2、3 操作输出一行一个整数,表示答案。

样例 #1

样例输入 #1

4 4
1 2 3 4
1 2
2 3
3 4
2 1 4
1 1 4 5
2 1 4
3 2

样例输出 #1

10
30
24

数据规模与约定

数据范围 说明
1≤n,q≤1051 \le n,q \le 10^5 结点数与操作数
0≤wi,k≤10000 \le w_i,k \le 1000 点权与增量
  • 路径操作 O(log⁡2n)O(\log^2 n),子树操作 O(log⁡n)O(\log n)(子树在 DFS 序上连续)。