E - Company Organization and Salaries Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は、ある会社の人事部門で働くデータアナリストです。この会社には N 人の社員が所属しており、それぞれ 1 から N までの社員番号が付けられています。

この会社では、社員の間に上司・部下の関係が存在します。各社員 i （ 2 \leq i \leq N ）にはちょうど 1 人の直属の上司 P_i がおり、 P_i < i が保証されています。社員 1 は社長であり、直属の上司を持ちません。この関係は、社員 1 を根とする根付き木を形成します。

社員 u が社員 v の部下であるとは、根付き木において u が v の子孫であること、すなわち v から根に向かう経路上に u は含まれないが、u から根に向かう経路上に v が含まれることを指します。言い換えると、社員 u から直属の上司の関係を 1 回以上たどることで社員 v に到達できるとき、かつそのときに限り、u は v の部下です。なお、社員 v 自身は社員 v の部下には含みません。

各社員 i には給与を表す正の整数値 A_i が定められています。

高橋君は、組織の分析のために、以下の 2 種類のクエリを合計 Q 回処理する必要があります。各クエリは与えられた順に逐次処理され、更新クエリによる変更はそれ以降のすべてのクエリに反映されます。

クエリ1（更新）: 1 v x — 社員 v の給与を 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は 1 つ以上存在する
  • 入力はすべて整数である

入力

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
  • 1 行目には、社員の人数を表す整数 N とクエリの個数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各社員の初期給与 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
  • 3 行目には、社員 2 から社員 N までの直属の上司を表す整数 P_2, P_3, \ldots, P_N がスペース区切りで与えられる。ただし N = 1 のとき、この行には何も書かれていない（空行が与えられる）。
  • 続く Q 行にわたり、各クエリが 1 行ずつ与えられる。
  • クエリ1の場合: 1 v x の形式で、社員番号 v と新しい給与 x がスペース区切りで与えられる。
  • クエリ2の場合: 2 v の形式で、社員番号 v が与えられる。

出力

クエリ2が与えられるたびに、社員 v の部下のうち社員 v の給与よりも厳密に大きい給与を持つ者の人数を 1 行に出力せよ。部下が 1 人もいない場合は 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

Score : 466 pts

Problem Statement

Takahashi is a data analyst working in the human resources department of a company. The company has N employees, each assigned an employee number from 1 to N.

In this company, there exist boss-subordinate relationships among employees. Each employee i (2 \leq i \leq N) has exactly one direct boss P_i, and it is guaranteed that P_i < i. Employee 1 is the president and has no direct boss. This relationship forms a rooted tree with employee 1 as the root.

Employee u is a subordinate of employee v if u is a descendant of v in the rooted tree. In other words, v is not on the path from v to the root that includes u, but v is on the path from u to the root. More precisely, u is a subordinate of v if and only if employee v can be reached from employee u by following the direct boss relationship one or more times. Note that employee v itself is not considered a subordinate of employee v.

Each employee i has a positive integer value A_i representing their salary.

For organizational analysis, Takahashi needs to process a total of Q queries of the following two types. Each query is processed sequentially in the given order, and changes made by update queries are reflected in all subsequent queries.

Query 1 (Update): 1 v x — Change the salary of employee v to x.

Query 2 (Investigation): 2 v — Among all subordinates of employee v, find and output the number of those whose salary is strictly greater than the salary of employee v at the time the query is processed.

Constraints

  • 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)
  • For Query 1, 1 \leq v \leq N and 1 \leq x \leq 10^9
  • For Query 2, 1 \leq v \leq N
  • There is at least one Query 2
  • All input values are integers

Input

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
  • The first line contains the integer N representing the number of employees and the integer Q representing the number of queries, separated by a space.
  • The second line contains the initial salaries A_1, A_2, \ldots, A_N of each employee, separated by spaces.
  • The third line contains the integers P_2, P_3, \ldots, P_N representing the direct bosses of employees 2 through N, separated by spaces. When N = 1, this line is empty (an empty line is given).
  • The following Q lines each contain one query.
  • For Query 1: Given in the format 1 v x, where the employee number v and the new salary x are separated by spaces.
  • For Query 2: Given in the format 2 v, where the employee number v is given.

Output

For each Query 2, output on a single line the number of subordinates of employee v whose salary is strictly greater than the salary of employee v. If employee v has no subordinates, output 0.

Sample Input 1

5 5
10 5 15 8 3
1 1 2 2
2 1
2 2
1 5 20
2 2
2 1

Sample Output 1

1
1
2
2

Sample Input 2

4 4
5 10 3 7
1 2 2
2 3
2 4
1 3 100
2 2

Sample Output 2

0
0
1

Sample Input 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

Sample Output 3

5
4
1
5
2
0

Sample Input 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

Sample Output 4

5
2
4
0
2
3
2
2
2
0

Sample Input 5

1 3
42

1 1 100
2 1
1 1 1

Sample Output 5

0