4765. 普通计算姬
#4765. 普通计算姬
题目描述
"奋战三星期，造台计算机"。小G响应号召，花了三小时造了台普通计算姬。普通计算姬比普通计算机要厉害一些
。普通计算机能计算数列区间和，而普通计算姬能计算树中子树和。更具体地，小G的计算姬可以解决这么个问题
：给定一棵n个节点的带权树，节点编号为1到n，以root为根，设sum[p]表示以点p为根的这棵子树中所有节点的权
值和。计算姬支持下列两种操作:
1 给定两个整数u,v，修改点u的权值为v。
2 给定两个整数l,r，计算sum[l]+sum[l+1]+....+sum[r-1]+sum[r]
尽管计算姬可以很快完成这个问题，可是小G并不知道它的答案是否正确，你能帮助他吗？
输入格式
第一行两个整数n,m，表示树的节点数与操作次数。
接下来一行n个整数，第i个整数di表示点i的初始权值。
接下来n行每行两个整数ai,bi，表示一条树上的边，若ai=0则说明bi是根。
接下来m行每行三个整数，第一个整数op表示操作类型。
若op=1则接下来两个整数u,v表示将点u的权值修改为v。
若op=2则接下来两个整数l,r表示询问。
N<=10^5,M<=10^5
0<=Di,V<2^31,1<=L<=R<=N,1<=U<=N
输出格式
对每个操作类型2输出一行一个整数表示答案。
样例
样例输入
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