8765: BZOJ4765:普通计算姬

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: