概要

木構造上で与えられた2点間のパス上の標高列について、最長の狭義単調減少部分列の長さを求めるクエリに答える問題です。

考察

この問題では、木上の任意の2点間のパスを取り出し、そのパス上の標高列に対して「最長狭義単調減少部分列（Longest Decreasing Subsequence）」を求めることになります。

素朴なアプローチとその問題点

素朴には、各クエリごとに以下のように処理できます： 1. 始点 \(u\) から終点 \(v\) へのパスをBFSやDFSなどで求め、 2. そのパス上の標高列を取り出し、 3. その列に対して最長狭義単調減少部分列を動的計画法などで求める。

しかし、これは1クエリあたり最悪 \(O(N)\) の計算が必要となり、全体で \(O(QN)\) となり制約下では時間内に収まりません。

改善策：LCAと最長減少部分列の高速計算

そこで以下の工夫を行います： - Lowest Common Ancestor（LCA） を使用して、効率的に木上のパスを求めます。 - パス上の標高列から最長狭義単調減少部分列を求める際に、貪欲法＋二分探索（LISの変形）を用いて高速化します。

LCAは前処理 \(O(N \log N)\)、各クエリ \(O(\log N)\) で求められ、最長減少部分列も列の長さを \(k\) として \(O(k \log k)\) で求められます。

これにより、全体で十分高速に動作するアルゴリズムが実現できます。

アルゴリズム

1. 木の構築と前処理

   • 隣接リストで木を構築。
   • 根（地点1）からDFS/BFSで各頂点の深さと親を求める。
   • Binary Liftingを用いてLCAを前処理（\(O(N \log N)\)）。

2. 各クエリ処理

   • クエリの始点 \(u\) と終点 \(v\) に対して、LCA \(l\) を求める。
   • パス \(u \to l \to v\) を構成するために、
     • \(u\) から親を辿って \(l\) まで進み、
     • \(v\) から親を辿って \(l\) まで進んだものを逆順にして連結。
   • 得られたパス上の標高列に対し、最長狭義単調減少部分列の長さを計算：
     • 貪欲＋二分探索のアルゴリズムを使用（LISの逆版）。
     • 各要素を負にして扱い、bisect を用いて挿入位置を管理。

計算量

• 時間計算量: \(O(N \log N + Q \cdot L \log L)\)
  （\(L\) はパスの長さ。最悪ケースで \(L = O(N)\)）
• 空間計算量: \(O(N \log N)\)

実装のポイント

• 木の構築時は無向グラフとして隣接リストを作成する。

• LCAのBinary Liftingテーブル up[i][k] は、頂点 \(i\) から \(2^k\) 個上の親を保持する。

• パス構築時にLCAを含めるのを忘れずに。

• 最長減少部分列の計算では、通常のLISとは異なり「狭義減少」なので、挿入時に重複を許さないようにする。

• bisect.bisect_left を使うことで、貪欲に最小の末尾を持つ部分列を選択できる。

  ソースコード

import sys
from collections import deque
import bisect

sys.setrecursionlimit(100000)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(data[idx]); idx += 1
    
    if N == 1:
        parents = []
    else:
        parents = [0] * (N + 1)
        for i in range(2, N + 1):
            parents[i] = int(data[idx]); idx += 1

    # Build adjacency list
    adj = [[] for _ in range(N + 1)]
    for i in range(2, N + 1):
        u = i
        v = parents[i]
        adj[u].append(v)
        adj[v].append(u)
    
    # Preprocessing: parent/depth/ancestors for LCA
    root = 1
    depth = [-1] * (N + 1)
    parent_list = [0] * (N + 1)
    order = []
    
    stack = [root]
    depth[root] = 0
    parent_list[root] = -1
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if depth[v] == -1:
                depth[v] = depth[u] + 1
                parent_list[v] = u
                stack.append(v)
    
    # Binary lifting for LCA
    LOG = 16
    up = [[-1] * LOG for _ in range(N + 1)]
    for i in range(1, N + 1):
        up[i][0] = parent_list[i]
    for k in range(1, LOG):
        for i in range(1, N + 1):
            if up[i][k - 1] != -1:
                up[i][k] = up[up[i][k - 1]][k - 1]
    
    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        for k in range(LOG):
            if diff & (1 << k):
                u = up[u][k]
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[u][k] != up[v][k]:
                u = up[u][k]
                v = up[v][k]
        return up[u][0]
    
    # Path from u to v: u -> lca -> v
    def get_path(u, v):
        l = lca(u, v)
        path = []
        x = u
        while x != l:
            path.append(x)
            x = parent_list[x]
        path.append(l)
        tmp = []
        x = v
        while x != l:
            tmp.append(x)
            x = parent_list[x]
        path.extend(tmp[::-1])
        return path

    results = []
    for _ in range(Q):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        path = get_path(u, v)
        heights = [H[node] for node in path]
        
        # Compute LIS in decreasing order using greedy with binary search
        # We maintain the smallest tail of all decreasing subsequences of length i+1
        tails = []
        for h in heights:
            pos = bisect.bisect_left(tails, -h)
            if pos == len(tails):
                tails.append(-h)
            else:
                tails[pos] = -h
        results.append(len(tails))
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。