ABC 165 F - LIS on Tree

問題

$n$ 頂点の木の各頂点に整数が書かれているとき、頂点 $0$ から各頂点へのパス上の整数からなる数列それぞれについて、最長増加部分列の長さを求めよ。

atcoder.jp

解説

まず、数列 $A$ の最長増加部分列の長さは以下の手順で求められる。

1. $DP _ i = \mathrm{inf}$ $(i = 0, \ldots, n - 1)$ とする。
2. 各 $a\in A$ について、$DP$ の中で $a$ 以上の最小の整数と $a$ を入れ替える。
3. $DP$ の $\mathrm{inf}$ でない整数の個数が $A$ の最長増加部分列の長さとなる。

例えば、$A=[2,3,1,5,4]$ のとき、 $$ \begin{aligned} a=2 &\to DP=[2,\mathrm{inf},\mathrm{inf},\mathrm{inf},\mathrm{inf}] \\ a=3 &\to DP=[2,3,\mathrm{inf},\mathrm{inf},\mathrm{inf}] \\ a=1 &\to DP=[1,3,\mathrm{inf},\mathrm{inf},\mathrm{inf}] \\ a=5 &\to DP=[1,3,5,\mathrm{inf},\mathrm{inf}] \\ a=4 &\to DP=[1,3,4,\mathrm{inf},\mathrm{inf}] \end{aligned} $$ となって、最長増加部分列の長さは $3$ となる。

今回の問題では、木の上でこの手順を行うので、深さ優先探索をしながら、行き止まりに来たら入れ替え操作を巻き戻しながら分岐点まで戻る、という操作を繰り返せばよい。

具体的には、深さ優先探索で使うスタック $Q$ で「次に訪問する点」と「$DP$ の中で入れ替えた位置と入れ替える前の値」の $2$ 通りの情報を管理し、$Q$ から取り出した情報がどちらの種類かによって操作を分ける。
前者の場合、$Q$ から取り出した点を $x$ として $DP$ の中で $A _ x$ 以上の最小の整数と $A _ x$ を入れ替え、その位置 $i$ と入れ替え前の $DP _ i$ のペアを $Q$ に追加し、$DP$ の $\mathrm{inf}$ でない整数の個数を記録する。さらに、$x$ の隣接点のうちまだ訪問していない点を $Q$ に追加する。
後者の場合、$Q$ から取り出した $(i,a)$ について $DP _ i$ を $a$ に戻す。

実装

「$x$ の隣接点のうちまだ訪問していない点を $Q$ に追加する」のところでは $a = -1$ として $(y,-1)$ を追加している。
配列 $L$ に $0$ から $i$ までのパス上の整数からなる数列の最長増加部分列の長さを記録している。

import bisect
n = int(input())
*A, = map(int, input().split())
G = [[] for i in range(n)]
for i in range(n - 1):
    x, y = map(int, input().split())
    G[x - 1].append(y - 1)
    G[y - 1].append(x - 1)
inf = 10**10
DP = [inf for i in range(n)]
L = [0 for i in range(n)]
V = [False for i in range(n)]
Q = [(0, -1)]
while Q:
    x, a = Q.pop()
    if a == -1:
        V[x] = True
        i = bisect.bisect_left(DP, A[x])
        Q.append((i, DP[i]))
        DP[i] = A[x]
        L[x] = bisect.bisect_left(DP, inf)
        for y in G[x]:
            if not V[y]:
                Q.append((y, -1))
    else:
        DP[x] = a
print(*L, sep='\n')

atcoder.jp