分数: 466 分
问题陈述
Takahashi 是一家公司人力资源部门的数据分析师。公司拥有 N 员工,每个员工分配一个员工编号 1 to N.
在该公司,员工之间存在上下级关系。每位员工 i (2 \leq i \leq N) 只有一个直接老板 P_i,并且保证 P_i < i。员工 1 是总裁,没有直接上司。这种关系与员工形成了一颗根深蒂固的树 1 作为根。
员工 u 是 下属 员工的 员工的 v if u 是 v 在有根树中。换句话说, v 不在来自的路径上 v 到包含的根 u,但是 v 位于以下路径上 u 到根。更准确地说, u 是以下机构的下属 v 当且仅当员工 可以从员工处联系 v 可以从员工那里联系到 u 遵循直接上司关系一次或多次。请注意,该员工 v 本身不被视为员工的下属 v.
每位员工 i 具有正整数值 A_i 代表他们的工资。
对于组织分析,Takahashi 总共需要处理 Q 以下两种类型的查询。每个查询都按照给定的顺序依次处理,更新查询所做的更改会反映在所有后续查询中。
查询1 (更新): 1 v x — 更改员工的工资 v to x.
查询2 (调查): 2 v — 在员工的所有下属中 v,查找并输出工资为的人数 严格大于 员工工资
处理查询时的 v 。
约束
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq P_i < i (2 \leq i \leq N)
- 对于查询 1, 1 \leq v \leq N 和 1 \leq x \leq 10^9
- 对于查询 2, 1 \leq v \leq N
- 至少有一个查询 2
- 所有输入值均为整数
输入
N Q
A_1 A_2 \cdots A_N
P_2 P_3 \cdots P_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
- 第一行包含整数 N 代表员工人数和整数 Q 代表查询数量,以空格分隔。
- 第二行包含初始工资 每个员工的 A_1, A_2, \ldots, A_N ,用空格分隔。
- 第三行包含整数 P_2, P_3, \ldots, P_N 代表员工的直接上司 2 通过 N,用空格分隔。当 N = 1,这一行是空的(给出了一个空行)。
- 以下 Q 行每一行包含一个查询。
- 对于查询 1:以格式给出
1 v x,其中员工编号 v 和新工资 x 用空格分隔。 - 对于查询 2:以格式给出
2 v,其中员工编号 v 。
输出
对于每个查询 2,在单行上输出员工的下属数量 v 其工资严格高于员工的工资 v。如果员工 v 没有下属,输出 0.
示例输入 1
5 5 10 5 15 8 3 1 1 2 2 2 1 2 2 1 5 20 2 2 2 1
示例输出 1
1 1 2 2
示例输入 2
4 4 5 10 3 7 1 2 2 2 3 2 4 1 3 100 2 2
示例输出 2
0 0 1
示例输入 3
10 8 50 30 70 20 60 10 80 40 90 55 1 1 2 2 3 3 4 4 5 2 1 2 2 2 3 1 4 100 2 2 1 1 85 2 1 2 5
示例输出 3
5 4 1 5 2 0
示例输入 4
20 15 100 90 80 70 60 50 40 30 20 10 110 120 130 140 150 55 65 75 85 95 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 2 1 2 2 2 3 1 1 200 2 1 1 11 500 2 5 1 5 1 2 5 2 4 1 10 999 2 9 2 1 1 3 1000 2 3
示例输出 4
5 2 4 0 2 3 2 2 2 0
示例输入 5
1 3 42 1 1 100 2 1 1 1 1
示例输出 5
0