QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 128 MB
Statistics

给定树上 $n$ 个点,每个点有一个点权 $v_i$。

在此题面中,启发式合并指,递归地进行从底往上的集合合并,每一次以集合的点权和为键值,将权值和更小的集合中的点加入更大的权值和的集合中,初始时每个点集合为该点本身。

同时我们钦定如下的枚举顺序:假设已经递归进行了所有子树的合并,合并当前层节点时从子树的根开始,将儿子们按编号大小从小到大排序,每一次合并两两集合得到子树的集合。

同时,若两个集合的权值和相同,以集合中最小节点深度为第二关键字进行比较(深度大的向深度小的合并)。

钦定该树的根为 $1$。给出以下查询和修改操作:

1 x 表示查询当前以 $x$ 为根的子树进行启发式合并后,没有进行「合并入另外一个集合」操作的节点权值。

2 x d将第 $x$ 个点的节点权值加 $d$。

输入格式

第一行两个整数 $n,q$,分别表示树的大小和操作次数。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$,其中 $a_i$ 表示结点 $i$ 的初始权值。

第三行 $n-1$ 个整数 $p_2,p_3,\cdots,p_n$,其中 $p_i$ 表示以结点 $1$ 为根时,结点 $i$ 的父亲。

接下来 $q$ 行,每行格式形如 1 x2 x d,分别对应题目描述中的两种操作。

输出格式

对于每个类型为 $1$ 的操作,输出一行一个整数,表示所求答案。

样例数据

样例输入

5 10
2 10 1 10 3
1 2 3 2
2 1 3
1 3
1 5
2 3 5
2 3 2
1 5
2 5 6
1 3
2 5 -1
2 3 0

样例输出

10
3
3
10

子任务

Idea:FutaRimeWoawaSete,Solution:zhoukangyang,Code:Rainybunny,Data:FutaRimeWoawaSete/Rainybunny

对于 $100\%$ 的数据,$1\le n,q\le2\times10^5$,$1\le p_i < i$;操作给出的 $x\in[1,n]$,$d\in[-10^{18},10^{18}]$;在任意时刻 $a_x\ge 1$ 且 $\sum_{x=1}^na_x\le10^{18}$。