この問題は、次の \(2\) つの要素に分けて解くことができます。

• 頂点 \(u\) から \(v\) へのパスを特定する。
• パス上の標高からなる列の最長減少部分列を計算する。

それぞれ、クエリあたり \(O(N)\) 時間と標高列の長さ \(L\) に対して \(O(L\log L)\) 時間で計算することができるため、この問題の制約のもと十分高速です。

最悪時間計算量は \(O(QN\log N)\) などになります。 一部の言語では非常に実行時間制限が厳しい場合があるので、高速な言語を使ったり、計算量をなるべく抑える工夫を行ったりする必要があるかもしれません。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;
    int N, Q;
    cin >> N >> Q;

    vector<int> H(N);
    for (int& h : H) {
        cin >> h;
    }
    vector<vector<int>> edges(N);
    for (int i = 1; i < N; ++i) {
        int p;
        cin >> p;
        --p; // 0-indexed にしておく
        edges[p].emplace_back(i);
        edges[i].emplace_back(p);
    }

    // DFS で答えを求める
    auto solve = [N, &H, &edges](this auto dfs, int now, int prev, int goal, vector<int>& dp) -> int {
        if (now == goal) {
            return ranges::lower_bound(dp, 0, greater{}) - begin(dp);
        }
        int ans = 0;
        for (int next : edges[now]) {
            if (next != prev) {
                int index = ranges::lower_bound(dp, H[next], greater{}) - begin(dp);
                int tmp = dp[index];
                dp[index] = H[next];
                ans = max(ans, dfs(next, now, goal, dp));
                dp[index] = tmp;
            }
        }
        return ans;
    };

    for (int i = 0; i < Q; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v; // 0-indexed にして

        vector<int> dp(N);
        dp[0] = H[u];
        // DFS して答えを出力
        cout << solve(u, u, v, dp) << endl;
    }
    return 0;
}

from bisect import bisect_left
from functools import lru_cache


N, Q = map(int, input().split())

H = list(map(int, input().split()))
edges = [[] for i in range(N)]
for i, p in enumerate(map(int, input().split())):
    p -= 1
    i += 1
    edges[p].append(i)
    edges[i].append(p)

path_from_root = [[] for i in range(N)]
path_from_root[0].append(0)
stack = [0]
while len(stack) > 0:
    now = stack[-1]
    stack.pop()
    for next in edges[now]:
        if len(path_from_root[next]) == 0:
            path_from_root[next] = [next] + path_from_root[now]
            stack.append(next)

# DFS で答えを求める
@lru_cache(maxsize=None)
def solve(start, goal):
    dp = []
    if len(path_from_root[start]) < len(path_from_root[goal]):
        level = len(path_from_root[goal]) - len(path_from_root[start])
        for u, v in zip(path_from_root[start], path_from_root[goal][level:]):
            x = bisect_left(dp, -H[u])
            if x == len(dp):
                dp.append(-H[u])
            else:
                dp[x] = -H[u]
            if u == v:
                break
            level += 1
        for v in reversed(path_from_root[goal][:level]):
            x = bisect_left(dp, -H[v])
            if x == len(dp):
                dp.append(-H[v])
            else:
                dp[x] = -H[v]
    else:
        level = len(path_from_root[start]) - len(path_from_root[goal])
        for u, v in zip(path_from_root[start][level:], path_from_root[goal]):
            x = bisect_left(dp, H[v])
            if x == len(dp):
                dp.append(H[v])
            else:
                dp[x] = H[v]
            if u == v:
                break
            level += 1
        for v in reversed(path_from_root[start][:level]):
            x = bisect_left(dp, H[v])
            if x == len(dp):
                dp.append(H[v])
            else:
                dp[x] = H[v]
    return len(dp)

for i in range(Q):
    u, v = map(int, input().split())
    u -= 1
    v -= 1 # 0-indexed にして

    print(solve(u, v)) # DFS して答えを出力