← 返回题目列表

AtCoder · awc0082_e

E. 公司组织和薪资

中文机器翻译题面 查看原题

分数: 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