#BZOJ4765. 普通计算姬

普通计算姬

题目描述

"奋战三星期,造台计算机"。小 G 响应号召,花了三小时造了台普通计算姬。普通计算姬比普通计算机要厉害一些。普通计算机能计算数列区间和,而普通计算姬能计算树中子树和。更具体地,小 G 的计算姬可以解决这么个问题:给定一棵 nn 个节点的带权树,节点编号为 11nn,以 rootroot 为根,设 sumpsum_p 表示以点 pp 为根的这棵子树中所有节点的权值和。

计算姬支持下列两种操作:

  1. 给定两个整数 u,vu,v,修改点 uu 的权值为 vv

  2. 给定两个整数 l,rl,r,计算 i=lrsumi\sum\limits_{i=l}^rsum_i

尽管计算姬可以很快完成这个问题,可是小 G 并不知道它的答案是否正确,你能帮助他吗?

输入格式

第一行两个整数 n,mn,m,表示树的节点数与操作次数。
接下来一行 nn个整数,第 ii 个整数 did_i 表示点 ii 的初始权值。
接下来 nn 行每行两个整数 ai,bia_i,b_i,表示一条树上的边,若 ai=0a_i=0 则说明 bib_i 是根。
接下来 mm 行每行三个整数,第一个整数 opop 表示操作类型。 若 op=1op=1 则接下来两个整数 u,vu,v 表示将点 uu 的权值修改为 vv 。若 op=2op=2 则接下来两个整数 l,rl,r 表示询问。

输出格式

对每个操作类型 22 输出一行一个整数表示答案。

6 4
0 0 3 4 0 1
0 1
1 2
2 3
2 4
3 5
5 6
2 1 2
1 1 1
2 3 6
2 3 5
16
10
9

数据规模与约定

对于 100%100\% 的数据,1n,m1051\le n,m\le 10^51di,v<2311\le d_i,v\lt 2^{31}1lrn1\le l\le r\le n1un1\le u \le n