概要

木上の2点間パスに沿った標高列から、最長の狭義単調減少部分列の長さを求める問題です。

考察

問題は木構造上で、2点間のパス上の標高列から最長狭義単調減少部分列（Longest Strictly Decreasing Subsequence, LSD）の長さを求めるものです。重要な観察点は以下の通りです：

1. 木構造は根付き木として与えられ、任意の2点間のパスは一意に定まります。
2. パスを求めるには、2点の最小共通祖先（LCA）を見つける必要があります。
3. 最長狭義単調減少部分列は、最長増加部分列（LIS）問題の逆バージョンであり、同様の動的計画法＋二分探索で効率的に解けます（\(O(k \log k)\)時間、\(k\)はパス長）。

素朴なアプローチとして、各クエリごとにパスを取得し、そのパス上の標高列に対して単純なDPを行うと、最悪ケースで\(O(Q \times k^2)\)時間となり、\(N, Q\)が最大5000である制約ではTLEとなります。しかし、LSD問題は二分探索を用いた効率的な解法（貪欲法＋二分探索）が知られており、各クエリを\(O(k \log k)\)で処理できます。

アルゴリズム

1. 前処理:
   • 各ノードの深さを計算します（根を深さ0として、親の深さ+1）。
   • LCAを求めるための単純な方法（深さを揃えてから共通祖先に達するまで登る）を採用します。
2. クエリ処理:
   • 各クエリ\((u, v)\)について、LCA \(w\)を求めます。
   • \(u\)から\(w\)までのパス（\(u\)から親を辿って\(w\)まで）と、\(w\)から\(v\)までのパス（\(v\)から親を辿って\(w\)まで、ただし逆順）を結合して、全体のパスを取得します。
   • パス上の標高列に対して、最長狭義単調減少部分列（LSD）の長さを求めます。
3. LSDの計算:
   • 貪欲法＋二分探索を用います。部分列の末尾を管理する配列tailsを維持します。
   • 各標高\(x\)について、tails中で\(x\)より小さい最大の値（つまりtailsは減少列となる）を二分探索で見つけ、適切な位置に\(x\)を配置します。これにより、最長減少部分列の長さが得られます。

計算量

• 時間計算量: \(O(Q \times (L + k \log k))\)。ここで\(L\)はLCAを求める時間（最大深さは\(O(N)\)）、\(k\)はパス長です。最悪ケースで\(k = O(N)\)なので、\(O(Q \times (N + N \log N)) = O(Q N \log N)\)となります。\(N, Q \leq 5000\)の制約では、\(5000 \times 5000 \times \log(5000) \approx 5000 \times 5000 \times 13 \approx 3.25 \times 10^8\)程度となり、C++等では厳しいですが、Pythonでは最適化された実装でギリギリ動作します。
• 空間計算量: \(O(N)\)（前処理で深さや親を格納するため）。

実装のポイント

• 再帰深度を上げる: sys.setrecursionlimit(10000)で再帰制限を緩和します（木の深さが最大5000になるため）。

• パスの構築: LCAを求めた後、\(u\)からLCAまでと、LCAから\(v\)までのパスを別々に取得し、結合します。

• LSDの計算: tails配列を減少列として維持するため、二分探索時に「tails[mid] > x」の場合に左側を探すようにします（減少列なので、大きい値ほど左に来ます）。これにより、\(x\)を置き換えるべき位置を正しく見つけられます。

  ソースコード

import sys
sys.setrecursionlimit(10000)

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); Q = int(next(it))
    H = [0] * (N+1)
    for i in range(1, N+1):
        H[i] = int(next(it))
    
    parent = [0] * (N+1)
    for i in range(2, N+1):
        p = int(next(it))
        parent[i] = p
    
    queries = []
    for i in range(Q):
        u = int(next(it)); v = int(next(it))
        queries.append((u, v))
    
    depth = [0] * (N+1)
    depth[1] = 0
    for i in range(2, N+1):
        depth[i] = depth[parent[i]] + 1
    
    def lca(u, v):
        while depth[u] > depth[v]:
            u = parent[u]
        while depth[v] > depth[u]:
            v = parent[v]
        while u != v:
            u = parent[u]
            v = parent[v]
        return u
    
    def get_path(u, v):
        w = lca(u, v)
        path1 = []
        while u != w:
            path1.append(u)
            u = parent[u]
        path1.append(w)
        path2 = []
        while v != w:
            path2.append(v)
            v = parent[v]
        path2.reverse()
        return path1 + path2
    
    def lis_decreasing(arr):
        if not arr:
            return 0
        tails = []
        for x in arr:
            left, right = 0, len(tails)
            while left < right:
                mid = (left + right) // 2
                if tails[mid] > x:
                    left = mid + 1
                else:
                    right = mid
            if left == len(tails):
                tails.append(x)
            else:
                tails[left] = x
        return len(tails)
    
    results = []
    for u, v in queries:
        path = get_path(u, v)
        arr = [H[node] for node in path]
        res = lis_decreasing(arr)
        results.append(str(res))
    
    sys.stdout.write("\n".join(results))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。