P96639

树上操作

难度 未定
讨论 统计 0通过 0提交 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

有一颗点数为N的树,以点1为根,且树点有边权。然后又M个操作,分为三种:

操作1:把某个结点x的点权增加a。

操作2:把某个结点x为根的子树中所有点的点权都增加a。

操作3:询问某个结点x到根的路径中所有点的点权和。

y:C9sX

输入

第一行包含两个整数N,M。表示点数和操作数。

接下来一行N个整数,表示树中结点的初始权值。

接下来N-1行每行三个正整数fr,to,表示该树中存在一条边(fr,to)。

再接下来M行,每行分别表示一次操作。其中第一个数表示该操作的种类(1~3),之后接这个操作的参数(x或者x a)。

paC

输出

对于每个询问操作,输出给询问的结果。结果之间用换行隔开。

 

样例

样例 1
输入
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
输出
6
9
13

来源

一本通

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交