8765: BZOJ4765：普通计算姬

"奋战三星期，造台计算机"。小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

提示

没有写明提示

题目来源

没有写明来源