abc 165 F - LIS on Tree (python)

dp の巻き戻しするやつ。dfs をして頂点を探索する際に、stack (deque) に次の頂点を入れる前に、dp を変更する前の要素を入れておくことで、dfs順に頂点を探索するときに、行き止まりについてから、一つ前の頂点に戻る時にその時点での dp を再現することができる。すごいね。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
from bisect import bisect_left

n = int(readline())
A = list(map(int,readline().split()))
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
que = deque()
inf = 10**9+1
dp = [inf]*n
que.append((0,-1))
chk = [False]*n
chk[0] = True
cnt = 0
ans = [1]*n

while que:
  now,d = que.pop()
  if d != -1:
    dp[now] = d
  else:
    ind = bisect_left(dp,A[now])
    que.append((ind,dp[ind]))
    dp[ind] = A[now]
    ans[now] = bisect_left(dp,inf)
    cnt += 1
    for i in g[now]:
      if not chk[i]:
        chk[i] = True
        que.append((i,-1))
  if cnt == n:
    break
        
print(*ans,sep='\n')