概要

木上の2点間パスを求め、そのパスに沿った標高列の最長狭義単調減少部分列（Longest Strictly Decreasing Subsequence, LDS）の長さを各クエリに対して求める問題です。

考察

問題の分解

この問題は大きく2つのステップに分かれます：

1. 木上の2点間パスの特定: 木構造なので、任意の2点 \(u, v\) 間のパスは一意に決まります。このパスは \(u\) から LCA（最小共通祖先）を経由して \(v\) に至る経路です。
2. 標高列の最長狭義単調減少部分列の計算: パス上の地点の標高を順に並べた列に対して、LDS を求めます。

LDS を LIS に帰着する

最長狭義単調減少部分列（LDS）は、列の各要素を 符号反転（\(-1\) 倍） することで、最長狭義単調増加部分列（LIS）の問題に帰着できます。

• 元の列: \(h_1 > h_2 > \cdots > h_m\)（狭義減少）
• 符号反転: \(-h_1 < -h_2 < \cdots < -h_m\)（狭義増加）

LIS は有名な \(O(k \log k)\) のアルゴリズム（bisect_left を用いる方法）で効率的に求められます。

計算量の見積もり

• \(N, Q \leq 5000\) と比較的小さいです。
• パスの長さは最大 \(O(N)\) です。
• 各クエリごとにパスを構築し LIS を求めても、1クエリあたり \(O(N \log N)\)、全体で \(O(QN \log N)\) 程度で十分間に合います。

アルゴリズム

1. LCA（最小共通祖先）の前処理

ダブリング（Binary Lifting）を用いて LCA を \(O(\log N)\) で求められるように前処理します。

• up[k][v]: 頂点 \(v\) から \(2^k\) 回親をたどった先の頂点
• depth[v]: 根（地点 \(1\)）からの深さ

LCA の求め方： 1. \(u, v\) の深さを揃える（深い方を引き上げる） 2. 同時に引き上げて一致する点を見つける

2. パスの構築

\(u\) から LCA \(l\) までの経路と、\(v\) から LCA \(l\) までの経路を求め、結合します。

• \(u \to l\): \(u\) から親を辿って \(l\) まで順に並べる → \([u, \ldots, l]\)
• \(l \to v\): \(v\) から親を辿って \(l\) まで並べたものを反転 → \([l\) の次の子, \(\ldots, v]\)

結合すると \([u, \ldots, l, \ldots, v]\) というパスが得られます。

3. LDS の計算

パス上の標高列 \(h_1, h_2, \ldots, h_k\) を得たら：

1. 各要素を \(-1\) 倍して \(-h_1, -h_2, \ldots, -h_k\) とする
2. この列に対して狭義単調増加の LIS を求める
3. bisect_left を使い、tails 配列を管理する標準的な \(O(k \log k)\) の LIS アルゴリズムを適用

具体例: パス上の標高が \([10, 5, 8, 3, 7, 2]\) の場合 - 狭義減少部分列の例: \([10, 8, 3, 2]\)（長さ4）、\([10, 5, 3, 2]\)（長さ4） - 最長は長さ 4

計算量

• 時間計算量: \(O(N \log N + Q \cdot N \log N)\)
  • LCA の前処理: \(O(N \log N)\)
  • 各クエリ: パス構築 \(O(N)\) + LIS 計算 \(O(N \log N)\)
  • 全体: \(O(QN \log N)\)（\(Q, N \leq 5000\) なので約 \(3 \times 10^8\) 未満で収まる）
• 空間計算量: \(O(N \log N)\)（ダブリングテーブル）

実装のポイント

• bisect_left で狭義増加 LIS を求める: bisect_left は「その値以上の最初の位置」を返すため、同じ値は上書きされ、狭義単調増加が正しく処理されます。もし広義（\(\leq\)）にしたい場合は bisect_right を使いますが、本問では狭義なので bisect_left が適切です。

• パスの結合時の重複に注意: \(u \to \text{LCA}\) のパスには LCA 自身を含め、\(v \to \text{LCA}\) のパスには LCA を含めずに反転して結合することで、LCA が二重に含まれることを防ぎます。

• \(u = v\) のケース: パスは1点のみとなり、LDS の長さは \(1\) です。特別な処理は不要で、一般のアルゴリズムで自然に処理されます。

  ソースコード

import sys
from bisect import bisect_left

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(input_data[idx]); idx += 1
    
    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    if N >= 2:
        for i in range(2, N + 1):
            p = int(input_data[idx]); idx += 1
            parent[i] = p
            children[p].append(i)
    
    # Precompute LCA using binary lifting
    LOG = 13
    up = [[0] * (N + 1) for _ in range(LOG)]
    depth = [0] * (N + 1)
    
    # BFS to compute depth and up[0]
    from collections import deque
    queue = deque([1])
    visited = [False] * (N + 1)
    visited[1] = True
    order = []
    while queue:
        v = queue.popleft()
        order.append(v)
        for c in children[v]:
            if not visited[c]:
                visited[c] = True
                depth[c] = depth[v] + 1
                up[0][c] = v
                queue.append(c)
    
    for k in range(1, LOG):
        for v in range(1, N + 1):
            up[k][v] = up[k-1][up[k-1][v]]
    
    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 >> k) & 1:
                u = up[k][u]
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u = up[k][u]
                v = up[k][v]
        return up[0][u]
    
    def get_path(u, v):
        l = lca(u, v)
        # Path from u to l
        path_u = []
        node = u
        while node != l:
            path_u.append(node)
            node = up[0][node]
        path_u.append(l)
        # Path from l to v (reversed)
        path_v = []
        node = v
        while node != l:
            path_v.append(node)
            node = up[0][node]
        # path is path_u + reversed(path_v)
        path_v.reverse()
        return path_u + path_v
    
    def lds_length(seq):
        # Longest strictly decreasing subsequence
        # = LIS of negated sequence (strictly increasing)
        # For strictly increasing LIS, use bisect_left on tails
        if not seq:
            return 0
        # We want longest strictly decreasing subsequence
        # Transform: negate values, find longest strictly increasing subsequence
        neg_seq = [-x for x in seq]
        # LIS strictly increasing
        tails = []
        for x in neg_seq:
            pos = bisect_left(tails, x)
            if pos == len(tails):
                tails.append(x)
            else:
                tails[pos] = x
        return len(tails)
    
    out = []
    for _ in range(Q):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        path = get_path(u, v)
        heights = [H[node] for node in path]
        out.append(str(lds_length(heights)))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。