概要

この問題は、木構造上の2点間のパス（最短経路）に含まれる標高の値を並べたとき、その列の最長狭義単調減少部分列 (LSDS) の長さを求める問題です。

考察

1. 問題の言い換え

「最長狭義単調減少部分列 (LSDS)」を求めることは、各要素の符号を反転させた（\(-H_i\) とした）列における「最長増加部分列 (LIS)」を求めることと同義です。一般的に LIS を求めるアルゴリズムの方が馴染み深いため、ここでは標高を負の値にして LIS を求める方針をとります。

2. 木上のパスの特定

木において、2地点 \(u, v\) 間のパスは、それらの最近共通祖先 (LCA: Lowest Common Ancestor) を経由する一意な経路です。 パスは以下の2つのパートに分けられます。 1. 始点 \(u\) から LCA までの上昇（親方向への移動） 2. LCA から終点 \(v\) までの下降（子方向への移動）

\(N, Q\) がともに \(5000\) と比較的小さいため、各クエリに対して愚直に親を辿ってパスを構築しても、計算量的に間に合わせることができます。

3. LIS（最長増加部分列）の計算

ある列の LIS の長さは、二分探索を用いた \(O(K \log K)\)（\(K\) は列の長さ）のアルゴリズムで効率的に求めることができます。 具体的には、tails[i] を「長さ \(i+1\) の増加部分列の末尾の最小値」として管理し、列の各要素 \(x\) に対して以下の操作を行います。 - tails の中で \(x\) 以上の最小の要素を二分探索で見つけ、それを \(x\) で更新する。 - もし \(x\) 以上の要素がなければ、tails の末尾に \(x\) を追加する。 最終的な tails の長さが LIS の長さになります。

アルゴリズム

1. 前処理:
   • すべての標高 \(H_i\) を \(-H_i\) に変換します。
   • 各地点の親 \(p_i\) と深さ（根からの距離）を計算しておきます。
2. クエリ処理 (各クエリ \(u, v\) について):
   • パスの構築:
     • \(u\) と \(v\) の深さを比較し、同じ深さになるまで深い方を親へ辿ります。
     • 深さが揃ったら、両者が一致するまで同時に親へ辿ります。一致した地点が LCA です。
     • この過程で、\(u \to \dots \to \text{LCA}\) の順の標高リストと、\(\text{LCA} \to \dots \to v\) の順の標高リストを作成します。
   • LIS の計算:
     • 構築したパス全体の標高列に対して、二分探索（bisect_left）を用いた LIS アルゴリズムを適用します。
   • 出力: LIS の長さを記録します。

計算量

• 時間計算量: \(O(Q \cdot N \log N)\)
  • 1クエリあたり、パスの抽出に \(O(N)\)、LIS の計算に \(O(N \log N)\) かかります。
  • \(N, Q \leq 5000\) のため、最悪ケースでも \(5000 \times 5000 \times \log(5000) \approx 3 \times 10^8\) 程度の操作回数となります。Python では少し重い処理ですが、パスの長さが常に \(N\) であるわけではないことや、定数倍が小さいため制限時間内に収まります。
• 空間計算量: \(O(N)\)
  • 木の構造や標高、パスの保存に \(O(N)\) の空間を使用します。

実装のポイント

• 高速な入出力: \(Q\) が大きいため、sys.stdin.read().split() や sys.stdout.write を使用して入出力を高速化しています。

• LCA の求め方: 制約 \(p_i < i\) により、ノード 1 を根として親を辿るだけで簡単に LCA を見つけることができます。

• パスの結合: \(u \to \text{LCA}\) のリストと、逆順にした \(v \to \text{LCA}\) のリスト（LCA を除く）を繋げることで、正しい順序のパスが得られます。

  ソースコード

import sys
from bisect import bisect_left

def solve():
    # Read all input data at once for speed
    data = sys.stdin.read().split()
    if not data:
        return
    
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    Q = int(data[ptr])
    ptr += 1
    
    # Pre-negate elevations to find the Longest Strictly Decreasing Subsequence (LSDS)
    # as the Longest Strictly Increasing Subsequence (LIS) of the negated elevations.
    neg_H = [0] * (N + 1)
    for i in range(1, N + 1):
        neg_H[i] = -int(data[ptr])
        ptr += 1
        
    # Precompute parents and depths. Node 1 is the root.
    # The constraint p_i <= i-1 ensures that when we process node i, its parent p_i is already processed.
    parent = [0] * (N + 1)
    depth = [0] * (N + 1)
    for i in range(2, N + 1):
        p = int(data[ptr])
        ptr += 1
        parent[i] = p
        depth[i] = depth[p] + 1
        
    # Local references for slightly faster access in tight loops
    bisect = bisect_left
    results = []
    
    for _ in range(Q):
        u = int(data[ptr])
        ptr += 1
        v = int(data[ptr])
        ptr += 1
        
        curr_u, curr_v = u, v
        u_path = []
        v_path = []
        u_path_append = u_path.append
        v_path_append = v_path.append
        
        u_depth = depth[curr_u]
        v_depth = depth[curr_v]
        
        # Traverse up from u and v to find their Lowest Common Ancestor (LCA)
        # while storing elevations along the paths.
        while u_depth > v_depth:
            u_path_append(neg_H[curr_u])
            curr_u = parent[curr_u]
            u_depth -= 1
        while v_depth > u_depth:
            v_path_append(neg_H[curr_v])
            curr_v = parent[curr_v]
            v_depth -= 1
        while curr_u != curr_v:
            u_path_append(neg_H[curr_u])
            v_path_append(neg_H[curr_v])
            curr_u = parent[curr_u]
            curr_v = parent[curr_v]
        
        # Add the LCA node elevation to the path from u to LCA
        u_path_append(neg_H[curr_u])
        
        # Calculate the LIS length on the sequence: u_path followed by reversed v_path.
        # This sequence represents the negated elevations along the path from u to v.
        tails = []
        tails_append = tails.append
        
        # Process the path from u to LCA
        for x in u_path:
            idx = bisect(tails, x)
            if idx == len(tails):
                tails_append(x)
            else:
                tails[idx] = x
        
        # Process the path from LCA to v (by iterating v_path in reverse)
        for j in range(len(v_path) - 1, -1, -1):
            x = v_path[j]
            idx = bisect(tails, x)
            if idx == len(tails):
                tails_append(x)
            else:
                tails[idx] = x
        
        results.append(str(len(tails)))
        
    # Output all results separated by newlines
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。