主题

主题

 
   

4765: 普通计算姬

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=4765

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


个人解法:

据说已经有大神在Minecraft里面造出了一台计算机,正在尝试用Minecraft里面的这台计算机再造一台计算机。

既然是查询编号区间,就按照编号分块。

如同大小分块般,预处理交集。具体来说,预处理出F[i][j],表示i这个节点的祖先属于j这个块的有多少个。

那么对于修改而言,我们可以直接维护块的答案。

对于查询而言,整块的部分,我们直接计算。

最后的问题是剩余零散的部分。这一部分我们可以尝试用一个DFS序。修改的时候顺便维护这个DFS序。查询的时候,找到子树,查询区间和即可。

爆long long。然后需要使用unsigned long long。然而刚开始不会输出unsigned long long,然后还是一个劲地WA……


关于处理F数组:

一趟DFS,x的数组直接抄Fa[x]的,然后把F[x][Belong[x]]++即可。

然而一开始,我是扫描每一个块,把块里面的元素打一个标记,然后DFS这棵树,计算一下。结果反复超时。我一直以为计算的时候的瓶颈,结果是预处理。

这两个算法理论复杂度是一样的,区别在于前者递归1次,后者递归O(Num)次。前者180ms,后者1800ms……


代码

 
 
评论