Preparing NOJ

普通计算姬

30000ms 262144K

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并不知道它的答案是否正确,你能帮助他吗?

Input:

第一行两个整数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

Output:

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

Sample Input:

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

Sample Output:

16
10
9

Info

BZOJ

Provider BZOJ

Origin BZOJ4765

Code BZOJ4765

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 08/25/2019 18:55:17

Related

Nothing Yet