D - Longest Descent Sequence on a Mountain Traverse Route Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は山岳地帯の縦走路を調査しています。この山岳地帯には N 個の地点があり、地点には 1 から N までの番号がついています。地点間は N-1 本の双方向の道で結ばれており、どの2地点間もちょうど1通りの経路で行き来できます（すなわち木構造をなしています）。

木の構造は、地点 1 を根としたときの各地点の親として与えられます。具体的には、地点 i（2 \leq i \leq N）の親は地点 p_i です。

各地点 i（1 \leq i \leq N）には標高 H_i が設定されています。異なる地点の標高が同じ値であることもあります。

高橋君は Q 回の経路調査を行います。各調査 j（1 \leq j \leq Q）では、始点 u_j と終点 v_j の2つの地点が指定されます（u_j = v_j であることもあります）。地点 u_j から地点 v_j への木上の一意なパスを考えます。このパス上の地点を u_j から v_j へ向かう順に a_1, a_2, \ldots, a_k とします。ここで k はパス上の地点数であり、a_1 = u_j、a_k = v_j です。u_j = v_j のときは k = 1、a_1 = u_j です。

このパスに対応する 標高列 h_1, h_2, \ldots, h_k を、各 t（1 \leq t \leq k）について h_t = H_{a_t} と定めます。

各調査について、この標高列の 最長狭義単調減少部分列の長さ を求めてください。

用語の定義

  • 列 h_1, h_2, \ldots, h_k の 部分列（subsequence） とは、1 \leq i_1 < i_2 < \cdots < i_m \leq k を満たす添字の組（m \geq 1）を選び、h_{i_1}, h_{i_2}, \ldots, h_{i_m} を元の順序のまま並べて得られる列のことです。選ぶ添字は元の列で連続している必要はありません。
  • 狭義単調減少部分列 とは、長さ m \geq 1 の部分列 h_{i_1}, h_{i_2}, \ldots, h_{i_m}（1 \leq i_1 < i_2 < \cdots < i_m \leq k）であって、h_{i_1} > h_{i_2} > \cdots > h_{i_m} を満たすものを指します。特に m = 1 のとき、この条件は自動的に満たされます。
  • 最長狭義単調減少部分列の長さ とは、すべての狭義単調減少部分列の中で長さ m が最大となるものの長さです。k \geq 1 であれば長さ 1 の部分列が必ず存在するため、最長狭義単調減少部分列の長さは必ず 1 以上です。

制約

  • 1 \leq N \leq 5000
  • 1 \leq Q \leq 5000
  • 1 \leq H_i \leq 10^9（1 \leq i \leq N）
  • 1 \leq p_i \leq i - 1（2 \leq i \leq N）
  • 1 \leq u_j, v_j \leq N（1 \leq j \leq Q）
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N Q
H_1 H_2 \ldots H_N
p_2 p_3 \ldots p_N
u_1 v_1
u_2 v_2
\vdots
u_Q v_Q
  • 1 行目には、地点の個数 N と調査の回数 Q が、スペース区切りで与えられる。
  • 2 行目には、各地点の標高 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。
  • 3 行目には、地点 i（2 \leq i \leq N）の親の番号 p_2, p_3, \ldots, p_N が、この順にスペース区切りで与えられる。N = 1 の場合は親情報が存在しないため、この行は空行となる。
  • 続く Q 行のうち j 行目（1 \leq j \leq Q）には、j 番目の調査の始点 u_j と終点 v_j がスペース区切りで与えられる。

出力

Q 行出力せよ。j 行目（1 \leq j \leq Q）には、j 番目の調査における、地点 u_j から地点 v_j へのパス上の標高列の最長狭義単調減少部分列の長さを整数で出力せよ。

入力例 1

5 4
10 30 20 40 5
1 1 2 2
4 3
4 5
1 1
3 4

出力例 1

3
3
1
2

入力例 2

6 5
5 5 5 5 5 5
1 1 2 2 3
1 6
4 5
2 3
6 4
1 1

出力例 2

1
1
1
1
1

入力例 3

10 8
100 80 90 60 70 50 40 30 20 10
1 1 2 2 3 3 4 4 5
7 9
1 10
10 7
4 6
8 9
3 2
5 6
1 1

出力例 3

4
4
3
3
2
2
3
1

入力例 4

20 15
50 40 60 30 70 20 80 10 90 5 55 45 65 35 75 25 85 15 95 1
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
15 16
1 20
7 18
3 2
11 14
20 19
9 10
13 12
17 8
5 6
1 1
19 20
4 15
6 11
2 9

出力例 4

6
4
6
3
3
3
3
2
2
3
1
5
2
3
2

入力例 5

1 1
1000000000

1 1

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is surveying a traverse route through a mountainous region. There are N points in this mountainous region, numbered from 1 to N. The points are connected by N-1 bidirectional paths, and any two points can be reached from each other by exactly one route (i.e., they form a tree structure).

The tree structure is given by specifying the parent of each point when point 1 is the root. Specifically, the parent of point i (2 \leq i \leq N) is point p_i.

Each point i (1 \leq i \leq N) has an elevation H_i. Different points may have the same elevation.

Takahashi conducts Q route surveys. In each survey j (1 \leq j \leq Q), a starting point u_j and an ending point v_j are specified (it is possible that u_j = v_j). Consider the unique path on the tree from point u_j to point v_j. Let the points on this path, listed in order from u_j to v_j, be a_1, a_2, \ldots, a_k. Here, k is the number of points on the path, with a_1 = u_j and a_k = v_j. When u_j = v_j, we have k = 1 and a_1 = u_j.

The elevation sequence corresponding to this path is defined as h_1, h_2, \ldots, h_k, where h_t = H_{a_t} for each t (1 \leq t \leq k).

For each survey, find the length of the longest strictly decreasing subsequence of this elevation sequence.

Definitions

  • A subsequence of a sequence h_1, h_2, \ldots, h_k is a sequence obtained by choosing a set of indices (m \geq 1) satisfying 1 \leq i_1 < i_2 < \cdots < i_m \leq k, and listing h_{i_1}, h_{i_2}, \ldots, h_{i_m} in their original order. The chosen indices do not need to be consecutive in the original sequence.
  • A strictly decreasing subsequence is a subsequence h_{i_1}, h_{i_2}, \ldots, h_{i_m} of length m \geq 1 (1 \leq i_1 < i_2 < \cdots < i_m \leq k) satisfying h_{i_1} > h_{i_2} > \cdots > h_{i_m}. In particular, when m = 1, this condition is automatically satisfied.
  • The length of the longest strictly decreasing subsequence is the maximum length m among all strictly decreasing subsequences. Since a subsequence of length 1 always exists when k \geq 1, the length of the longest strictly decreasing subsequence is always at least 1.

Constraints

  • 1 \leq N \leq 5000
  • 1 \leq Q \leq 5000
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq p_i \leq i - 1 (2 \leq i \leq N)
  • 1 \leq u_j, v_j \leq N (1 \leq j \leq Q)
  • All input values are integers.

Input

The input is given from standard input in the following format:

N Q
H_1 H_2 \ldots H_N
p_2 p_3 \ldots p_N
u_1 v_1
u_2 v_2
\vdots
u_Q v_Q
  • The first line contains the number of points N and the number of surveys Q, separated by a space.
  • The second line contains the elevations H_1, H_2, \ldots, H_N of each point, separated by spaces.
  • The third line contains the parent numbers p_2, p_3, \ldots, p_N of points i (2 \leq i \leq N), in this order, separated by spaces. When N = 1, there is no parent information, so this line is an empty line.
  • In the following Q lines, the j-th line (1 \leq j \leq Q) contains the starting point u_j and ending point v_j of the j-th survey, separated by a space.

Output

Output Q lines. On the j-th line (1 \leq j \leq Q), output as an integer the length of the longest strictly decreasing subsequence of the elevation sequence along the path from point u_j to point v_j in the j-th survey.

Sample Input 1

5 4
10 30 20 40 5
1 1 2 2
4 3
4 5
1 1
3 4

Sample Output 1

3
3
1
2

Sample Input 2

6 5
5 5 5 5 5 5
1 1 2 2 3
1 6
4 5
2 3
6 4
1 1

Sample Output 2

1
1
1
1
1

Sample Input 3

10 8
100 80 90 60 70 50 40 30 20 10
1 1 2 2 3 3 4 4 5
7 9
1 10
10 7
4 6
8 9
3 2
5 6
1 1

Sample Output 3

4
4
3
3
2
2
3
1

Sample Input 4

20 15
50 40 60 30 70 20 80 10 90 5 55 45 65 35 75 25 85 15 95 1
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
15 16
1 20
7 18
3 2
11 14
20 19
9 10
13 12
17 8
5 6
1 1
19 20
4 15
6 11
2 9

Sample Output 4

6
4
6
3
3
3
3
2
2
3
1
5
2
3
2

Sample Input 5

1 1
1000000000

1 1

Sample Output 5

1