Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices, whose i-th edge connects Vertex u_i and Vertex v_i.
Vertex i has an integer a_i written on it.
For every integer k from 1 through N, solve the following problem:

We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex 1 to Vertex k, in the order they appear. Find the length of the longest increasing subsequence of this sequence.

Here, the longest increasing subsequence of a sequence A of length L is the subsequence A_{i_1} , A_{i_2} , ... , A_{i_M} with the greatest possible value of M such that 1 \leq i_1 < i_2 < ... < i_M \leq L and A_{i_1} < A_{i_2} < ... < A_{i_M}.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq a_i \leq 10^9

1 \leq u_i , v_i \leq N

u_i \neq v_i

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}

Output

Print N lines. The k-th line, print the length of the longest increasing subsequence of the sequence obtained from the shortest path from Vertex 1 to Vertex k.

Sample Input 1

10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10

Sample Output 1

1
2
3
3
4
4
5
2
2
3

For example, the sequence A obtained from the shortest path from Vertex 1 to Vertex 5 is 1,2,5,3,4. Its longest increasing subsequence is A_1, A_2, A_4, A_5, with the length of 4.



Sample input:
10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10


Sample output:
1
2
3
3
4
4
5
2
2
3

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    dp = [float('inf')] * (N+2)
    dp[0] = -float('inf')
    ddp2 = [0]
    paths = []
    actions = []# (idx, pre, pro)
    ans = [0] * (N+1)
    def dfs(node, parent=None):

        a = A[node]
        seen[node] = True
        if parent == None:
            actions.append((1, dp[1], a, 1))
            dp[1] = a
            ddp2[0] += 1
        else:
            idx = bin_search(dp, a)
            if dp[idx] == float('inf'):
                actions.append((idx, dp[idx], a, 1))
                ddp2[0] += 1
            else:
                actions.append((idx, dp[idx], a, 0))
            dp[idx] = a
        ans[node] = ddp2[0]
        for next in to[node]:
            if not seen[next]:
                dfs(next, node)

        idx, pre, pro, change = actions.pop()
        dp[idx] = pre
        ddp2[0] -= change

    dfs(1)
    for s in ans[1:]:
        print(s)
    return None

def bin_search(A, x):
    '''
    return index which is lowest in values more than or equal to x
    '''
    low = 0
    high = len(A) - 1
    c = (low + high) // 2
    if A[-1] < x: return float('inf')
    while high - low > 1:
        if A[c] < x:
            low = c
            c = (low + high) // 2

        elif A[c] > x:
            high = c
            c = (high + low) // 2
        else:
            return c
    return high

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=list(map(int,input().split()))
edge=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=map(int,input().split())
    u-=1
    v-=1
    edge[u].append(v)
    edge[v].append(u)
stack=deque([])
inf=10**18
lis=[inf]*(n+1)
ans=[0 for _ in range(n)]
visited=[True]*n
#print(edge)
def dfs(s):
    visited[s]=False
    idx=bisect_left(lis,a[s])
    stack.append((idx,lis[idx]))
    lis[idx]=a[s]
    ans[s]=bisect_left(lis,inf)
    for x in edge[s]:
        if visited[x]:
            dfs(x)
    idx,val=stack.pop()
    lis[idx]=val
dfs(0)
#print(lis)
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import bisect
INF = 2**31 - 1

n = int(input())
A = list(map(int, input().split()))
T = [[] for _ in range(n)]
for _ in range(n-1):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  T[u].append(v)
  T[v].append(u)
stack = []
L = [INF]*n
ans = [0]*n
def dfs(v, par=-1):
  a = A[v]
  idx = bisect.bisect_left(L, a)
  stack.append((idx, L[idx]))
  L[idx] = a
  ans[v] = bisect.bisect_left(L, INF)
  for nv in T[v]:
    if nv != par:
      dfs(nv, v)
  b, c = stack.pop()
  L[b] = c
dfs(0)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
#入力高速化 + 再帰回数制限解除
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)

from bisect import bisect_left,bisect_right
n=int(input())
a=list(map(int,input().split()))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  u,v=map(int,input().split())
  u-=1
  v-=1
  edge[u].append(v)
  edge[v].append(u)
ans=[-1]*n
dp=[10**10]*n

#オイラーツアー
#n=頂点数、s=始点、edge=隣接リスト
#木構造を投げると訪問順listが帰ってくる、|ans|=2*n-1
#適宜書き換えて実装を楽にしましょう
def EulerTour(n,s,e):
  EulerTour_list=[]
  def EulerTour_dfs(i,root):
    EulerTour_list.append(i)
    ind=bisect_left(dp,a[i])
    bef=dp[ind]
    dp[ind]=a[i]
    ans[i]=bisect_left(dp,10**10)
    for j in e[i]:
      if j!=root:
        EulerTour_dfs(j,i)
    if root!=-1:
      EulerTour_list.append(root)
      dp[ind]=bef
  EulerTour_dfs(s,-1)
  return EulerTour_list

EulerTour(n,0,edge)
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))

G = [[] for _ in range(N)]

for _ in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)


root = 0

ans = [0] * N
check = [False] * N
check[root] = True

memo = [None] * N

INF = 10 ** 10
dp = [INF] * N

def dfs(x):
    tmp = bisect_left(dp, A[x])
    memo[x] = (tmp, dp[tmp])
    dp[tmp] = A[x]
    ans[x] = bisect_left(dp, INF)
    for next_ in G[x]:
        if check[next_]:
            continue
        check[next_] = True
        dfs(next_)
    j, a = memo[x]
    dp[j] = a

dfs(root)

print (*ans, sep = '\n')

Submission status: Accepted

Solution code:
# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit(10**7)

INF = 10**18

n = int(input())
a = list(int(x) for x in input().split())
g = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * n
dfs(0, -1)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))

edges = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    fr, to = map(int, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

order = []
parent = [-1] * (N + 1)
st = [1]
while st:
    now = st.pop()
    order.append(now)
    if now > 0:
        st.append(-now)
        for to in edges[now]:
            if to == parent[now]:
                continue
            st.append(to)
            parent[to] = now

L = [-10**18]
ans = [-1] * (N + 1)
st = [(-1, -1)] * (N + 1)

for now in order:
    if now < 0:
        val, idx = st[-now]
        if val == -1:
            L.pop()
        if val > 0:
            L[idx] = val
        continue

    a = A[now - 1]
    i = bisect_left(L, a)

    if len(L) == i:
        L.append(a)
    else:
        st[now] = (L[i], i)
        if L[i] > a:
            L[i] = a

    ans[now] = len(L) - 1

print(*ans[1:], sep='\n')

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = list(map(int, input().split()))

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

ans = [0] * N
L = [-10**18]

def search(now, pr):
    a = A[now]
    i = bisect_left(L, a)
    isAppended = False
    prevValue = -1

    if i == len(L):
        L.append(a)
        isAppended = True
    else:
        prevValue = L[i]
        if L[i] > a:
            L[i] = a

    ans[now] = len(L) - 1

    for to in edges[now]:
        if to == pr:
            continue
        search(to, now)

    if isAppended:
        L.pop()
    else:
        L[i] = prevValue

search(0, -1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
g=[[]for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)

import sys
sys.setrecursionlimit(10**6)

lastdp=[10**9+1]*n
recode=[[10**9+1]for i in range(n)]
ans=[0]*n
from bisect import bisect_left
def rec(me,parent):
    global lastdp
    a=A[me]
    point=bisect_left(lastdp,a)
    recode[point].append(a)
    lastdp[point]=a
    tmpans=bisect_left(lastdp,10**9+1)
    ans[me]=tmpans

    for child in g[me]:
        if child!=parent:
            rec(child,me)

    recode[point].pop()
    lastdp[point]=recode[point][-1]
    return

rec(0,-1)
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left
from collections import defaultdict

sys.setrecursionlimit(1000000)

n = int(input())
a = [int(i) for i in input().split()]

nbs = [ [] for _ in range(n) ]

for _ in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = defaultdict(int)

def getmlen(cur, p):
    for ch in nbs[cur]:
        if ch == p:
            continue

        if a[ch] > dp[-1]:
            dp.append(a[ch])
            mlen[ch] = len(dp)
            getmlen(ch, cur)
            dp.pop(-1)
        else:
            idx = bisect_left(dp, a[ch])
            ov = dp[idx]
            dp[idx] = a[ch]
            mlen[ch] = len(dp)
            getmlen(ch, cur)
            dp[idx] = ov
            

dp = []
dp.append(a[0])
mlen[0] = 1
getmlen(0, -1)

for i in range(n):
    print(mlen[i])

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(input())
a = [int(i) for i in input().split()]

nbs = [ [] for _ in range(n) ]

for _ in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = [ 0 ] * n

def getmlen(cur, p):
    for ch in nbs[cur]:
        if ch == p:
            continue

        if a[ch] > dp[-1]:
            dp.append(a[ch])
            mlen[ch] = len(dp)
            getmlen(ch, cur)
            dp.pop(-1)
        else:
            idx = bisect_left(dp, a[ch])
            ov = dp[idx]
            dp[idx] = a[ch]
            mlen[ch] = len(dp)
            getmlen(ch, cur)
            dp[idx] = ov
            

dp = []
dp.append(a[0])
mlen[0] = 1
getmlen(0, -1)

for i in range(n):
    print(mlen[i])

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(input())
a = [int(i) for i in input().split()]

nbs = [ [] for _ in range(n) ]

for _ in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen = [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    for ch in nbs[cur]:
        if ch == p:
            continue

        idx = bisect_left(dp, a[ch])
        ov = dp[idx]

        ntail = max(ctail, idx)
        dp[idx] = a[ch]
        mlen[ch] = ntail + 1
        getmlen(ch, cur, ntail)
        dp[idx] = ov

        

dp[0] = a[0]
mlen[0] = 1
getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

n = int(input())
a = [int(i) for i in input().split()]

nbs = [ [] for _ in range(n) ]

for _ in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    for ch in nbs[cur]:
        if ch == p:
            continue

        idx = bisect_left(dp, a[ch])
        ov = dp[idx]

        ntail = max(ctail, idx)
        dp[idx] = a[ch]
        mlen[ch] = ntail + 1
        getmlen(ch, cur, ntail)
        dp[idx] = ov

        

dp[0] = a[0]
mlen[0] = 1
getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print(ret[i])

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 6)

N = int(input())
A = list(map(int, input().split()))
dp = [float('inf')] * N
tree = defaultdict(list)
for _ in range(N - 1):
	u, v = list(map(int, input().split()))
	tree[u-1].append(v-1)
	tree[v-1].append(u-1)

dp[0] = A[0]
ans = [float('inf')] * N
ans[0] = 1
def backtrack(node, visited, tail_idx):
	flag = any([nx not in visited for nx in tree[node]])
	if not flag:
		return
	for nx in tree[node]:
		if nx in visited:
			continue
		visited.add(nx)
		idx = bisect_left(dp, A[nx])
		prev = dp[idx]
		if tail_idx < idx:
			dp[idx] = A[nx]
			new_tail_idx = idx
			ans[nx] = min(new_tail_idx + 1, ans[nx])
			backtrack(nx, visited, new_tail_idx)
		elif A[nx] < dp[idx]:
			dp[idx] = A[nx]
			ans[nx] = min(tail_idx + 1, ans[nx])
			backtrack(nx, visited, tail_idx)
		else:
			ans[nx] = min(tail_idx + 1, ans[nx])
			backtrack(nx, visited, tail_idx)
		dp[idx] = prev
		visited.remove(nx)

backtrack(node=0, visited={0}, tail_idx=0)
for i in ans:
	print(i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left

N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)

lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v

dfs(0, -1)

ret[0] = 1
for i in range(N) :
  print(ret[i])

Submission status: Accepted

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**7)

n = int(input())
a = [0]+list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)

m = 10**18
dp = [m]*(n+1)
ans = [1]*(n+1)
checked = [False]*(n+1)
checked[1] = True
changes = []

def search(x):
    ind = bisect.bisect_left(dp,a[x])
    changes.append((ind,dp[ind]))
    dp[ind] = a[x]
    ans[x] = bisect.bisect_left(dp,m)
    
    for i in t[x]:
        if not checked[i]:
            checked[i] = True
            search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

N = int(input())
A = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)
INF=float('inf')
dp = [INF] * (N + 1)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N

# DFS
q = deque([(0, 0)])  # (current, parent)
while q:
    u, p = q.pop()

    # Roll back
    if p is None:
        i, x = rb[u].pop()
        dp[i] = x
        continue

    # Update dp
    i = bisect_left(dp, A[u])
    rb[u].append((i, dp[i]))
    dp[i] = A[u]

    # Calc ans
    ans[u] = max(i,ans[p])

    # Go to next
    q.append((u, None))
    for v in graph[u]:
        if v == p:
            continue
        q.append((v, u))

print(*ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)

def input(): return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

# log(n)
# log(A)

edges = [ [] for _ in range(n+1) ]
# for _ in range(n-1):
for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    # line = input()
    # log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)

def input(): return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

# log(n)
# log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
# for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input()
    # log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)

# def input(): return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

# log(n)
# log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
#for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input().strip()
    # log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)

def input(): return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

# log(n)
# log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
#for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input().strip()
    # log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

import numpy as np


INF = 10 ** 10

# input
N = int(input())
A = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(N - 1)]

# link
link = [[] for _ in range(N + 1)]
for u, v in uv:
    link[u].append(v)
    link[v].append(u)


def dfs(l, dp, pre, v):
    # LIS
    idx = np.searchsorted(dp, A[v - 1])
    l[v] = max(idx, l[pre])
    bef = dp[idx]
    dp[idx] = A[v - 1]
    
    for x in link[v]:
        if x != pre:
            dfs(l, dp, v, x)

    dp[idx] = bef


def main():
    l = [0] * (N + 1)
    dp = np.full(N + 1, INF)
    dp[0] = 0
    dfs(l, dp, 0, 1)
    for ans in l[1:]:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

log(n)
log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
#for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input().strip()
    log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
# input = sys.stdin.readline

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

log(n)
log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
#for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input()
    log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

log(n)
log(A)

edges = [ [] for _ in range(n+1) ]
for _ in range(n-1):
#for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    line = input()
    log(line)
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
# sys.stdin.readline

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999

n = int(input())
A = [-INF] + get_nums_l()

edges = [ [] for _ in range(n+1) ]
for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
# dp[0]は使用しないので負の無限大を入れておく
dp = [INF] * (n+1)
dp[0] = -INF

dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
# sys.stdin.readline

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n = int(input())
A = [-INF] + get_nums_l()
edges = [ [] for _ in range(n+1) ]
for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
dp = [INF] * (n+1)
dp[0] = -INF
dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import bisect
import copy
from collections import deque
sys.setrecursionlimit(10**7)

def main():
    N = int(input())
    a = list(map(int,input().split()))
    INF = 10**12
    
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        u,v = map(int,input().split())
        edge[u-1].append(v-1)
        edge[v-1].append(u-1)
        
    def LIS(dp,num):
        ind = bisect.bisect_left(dp,num)
        ret = dp[ind]
        dp[ind] = num
        return ind,ret
    
    dp = [INF]*(N+2)
    dp[0] = -INF

    ans = [0]*N
    q = deque([])
    
    def DFS(prev,now,dp):
        while q:
            s,t,ind,num = q.pop()
            if t == prev:
                q.append((s,t,ind,num))
                break
            else:
                dp[ind] = num
        ind,num = LIS(dp,a[now])
        ans[now] = max(ind,ans[prev])
        q.append((prev,now,ind,num))
        for fol in edge[now]:
            if fol != prev:
                DFS(now,fol,dp)

    DFS(-1,0,dp)
    print(*ans,sep="\n")
 
if __name__ == "__main__":
    main()