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:
def examA():
    K = I()
    A, B = LI()
    for i in range(A,B+1):
        if i%K==0:
            print("OK")
            return
    print("NG")
    return

def examB():
    X = I()
    now = 100
    ans = 0
    while(now<X):
        ans += 1
        now += now//100
    print(ans)
    return

def examC():
    N, M, Q = LI()

    ans = 0
    print(ans)
    return

def examD():
    A, B, N = LI()
    if N>=B-1:
        ans = (A*(B-1))//B
    else:
        ans = (A*N)//B
    print(ans)
    return

def examE():
    N, M = LI()
    ans = []
    if N%2==1:
        for i in range(N // 2):
            ans.append((i + 1, N - i))
    else:
        flag = False
        for i in range(N // 2):
            if N-i-(i+1)<=N//2:
                flag = True
            if flag:
                ans.append((i+1,N-i-1))
            else:
                ans.append((i + 1, N - i))
    #print(ans)
    for v in ans[:M]:
        print(" ".join(map(str,v)))
    return

def examF():
    N = I()
    A = LI()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        u, v = LI()
        u -= 1; v -= 1
        V[u].append(v)
        V[v].append(u)
    dp = [-1]*N
    dp[0] = 1
    LIS = deque()
    LIS.append(A[0])
    def dfs(s):
        #print(LIS)
        for i in V[s]:
            if dp[i]!=-1:
                continue
            flag = []
            if A[i] > LIS[-1]:
                LIS.append(A[i])
                flag = False
            else:
                flag = [bisect.bisect_left(LIS, A[i]),LIS[bisect.bisect_left(LIS, A[i])]]
                LIS[flag[0]] = A[i]
            dp[i] = len(LIS)
            dfs(i)
            #print(flag)
            if not flag:
                LIS.pop()
            else:
                LIS[flag[0]] = flag[1]
        return
    dfs(0)
    ans = dp
    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n = int(input())
a = [int(i) for i in readline().split()]
m = map(int,read().split())

g = [[] for _ in range(n)]
for i,j in zip(m,m):
    g[i-1].append(j-1)
    g[j-1].append(i-1)

INF = 10**9

q = [~0,0]
dp = [INF]*n
ans = [0]*n
val = 0
idx = [-1]*n
old = [-1]*n
parent = [-1]*n

ss = 0
from bisect import bisect_left
while q:
    v = q.pop()
    if v >= 0:
        iv = idx[v] = bisect_left(dp,a[v])
        x = old[v] = dp[idx[v]]
        if x == INF: val += 1
        ans[v] = val

        dp[iv] = a[v]
        for c in g[v]:
            if c != parent[v]:
                parent[c] = v            
                q.append(~c)
                q.append(c)
    else:
        v = ~v
        x = dp[idx[v]] = old[v]
        if x == INF: val -= 1
    

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
A = [0] + list(map(int,input().split()))
C = [list(map(int,input().split())) for i in range(n-1)]


sys.setrecursionlimit(10**5 + 5)  # 再帰回数の上限！！


M = [[] for i in range(n+1)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])


# 0-indexedの場合
V = [0] * (n+1)
# D = [-1] * (n+1)  # 自分を含む、子孫のノード数
ANS = [0] * (n+1)

R = [10**10] * (n+5)

import bisect

R[0] = A[1]
ANS[1] = 1

def des(x):
    # end = 1
    V[x] = 1
    # print(R[:10])


    for i in M[x]:
        if V[i] == 0:
            # print(i)
            # end = 0
            V[i] = 1
            ind = bisect.bisect_left(R, A[i])
            ma = R[ind]
            R[ind] = A[i]
            ANS[i] = bisect.bisect_left(R, 10**10-1)
            des(i)
            R[ind] = ma

    # if end == 1:
    #     print(R)
    #     ANS[x] = bisect.bisect_right(R, 10**10-1)

des(1)

for i in range(1, len(ANS)):
    print(ANS[i])

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
a = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(n-1):
	u, v = map(int, input().split())
	adj[u-1].append(v-1)
	adj[v-1].append(u-1)

INF = 10**10
dp = [INF for _ in range(n)]
ans = [0 for _ in range(n)]

def dfs(x, p):
	ans[x] = bisect_left(dp, INF)
	for v in adj[x]:
		if v == p:
			continue
		ind = bisect_left(dp, a[v])
		pres = dp[ind]
		dp[ind] = a[v]
		dfs(v, x)
		dp[ind] = pres
	return

dp[0] = a[0]
dfs(0, -1)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class SegTree:
    def __init__(self, N, X_f, X_unit, X_commutative=False):
        self.N = N
        self.X_f = X_f
        self.X_unit = X_unit
        self.X = [self.X_unit] * (N + N)
        if X_commutative:
            self.fold = self._fold_commutative

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

    def _fold_commutative(self, L, R):
        L += self.N
        R += self.N
        v = self.X_unit
        while L < R:
            if L & 1:
                v = self.X_f(v, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                v = self.X_f(v, self.X[R])
            L >>= 1
            R >>= 1
        return v

N = int(readline())
A = (0, ) + tuple(map(int, readline().split()))

m = map(int, read().split())
U, V = zip(*zip(m, m))

def edges_to_graphdata(A, B, N, M):
    head = [-1] * (N + 1)
    nxt = [0] * (M + M)
    to = [0] * (M + M)
    for i in range(M):
        a = A[i]
        b = B[i]
        nxt[i << 1] = head[a]
        to[i << 1] = b
        head[a] = i << 1
        nxt[i << 1 | 1] = head[b]
        to[i << 1 | 1] = a
        head[b] = i << 1 | 1
    return head, nxt, to

def EulerTour(head, nxt, to, root=1):
    N = len(head) - 1
    parent = [0] * (N + 1)
    ind_L = [0] * (N + 1)
    ind_R = [0] * (N + 1)
    i = -1
    tour = []
    stack = [-root, root]
    stack[0] = -root
    stack[1] = root
    while stack:
        v = stack.pop()
        tour.append(v)
        i += 1
        if v > 0:
            ind_L[v] = i
            p = parent[v]
            k = head[v]
            while k != -1:
                w = to[k]
                if w == p:
                    k = nxt[k]
                    continue
                parent[w] = v
                stack.append(-w)
                stack.append(w)
                k = nxt[k]
        else:
            ind_R[-v] = i
    return tour, ind_L, ind_R, parent

tour, ind_L, ind_R, parent = EulerTour(*edges_to_graphdata(U, V, N, N - 1))

depth = [0] * (N + 1)
d = 0
for e in tour:
    d += 1 if e > 0 else -1
    if e > 0:
        depth[e] = d

A = [x * (N + N + 10) - d for x, d in zip(A, depth)]
A_unique = sorted(A)
A_rank = [bisect_left(A_unique, x) for x in A]

seg = SegTree(N + 1, max, 0, X_commutative=True)
LIS = [0] * (N + 1)
for e in tour:
    if e > 0:
        i = A_rank[e]
        LIS[e] = seg.fold(0, i + 1) + 1
        seg.set_val(i, LIS[e])
    else:
        i = A_rank[-e]
        seg.set_val(i, 0)

for e in tour:
    if e > 0:
        LIS[e] = max(LIS[e], LIS[parent[e]])

print('\n'.join(map(str, LIS[1:])))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left

INF = 10**17

N = int(input())
A = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)


stack = [0]
ans = [-1]*N
dp = [INF]*(N+1)
to_rev = [(-1, -1) for _ in range(N)]
while stack:
    p = stack.pop()
    if p >= 0:
        ind = bisect_left(dp, A[p])
        to_rev[p] = (ind, dp[ind])
        dp[ind] = A[p]
        ans[p] = bisect_left(dp, INF)
        stack.append(~p)
        for np in graph[p]:
            if ans[np] == -1:
                stack.append(np)
    else:
        p = ~p
        ind, score = to_rev[p]
        dp[ind] = score

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

Submission status: Accepted

Solution code:
import sys
from copy import copy
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n = int(input())
a = list(map(int, input().split()))

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

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


def dfs(v, v_p, dp_len):
    # print(v, v_p, dp)
    ans[v] = dp_len
    for v_next in graph[v]:
        if v_next == v_p:
            continue

        # print(dp)
        if a[v_next] > dp[dp_len - 1]:
            past = dp[dp_len]
            dp[dp_len] = a[v_next]
            dfs(v_next, v, dp_len + 1)
            dp[dp_len] = past
        else:
            idx = bisect_left(dp, a[v_next])
            # always idx < dp_len
            past = dp[idx]
            dp[idx] = a[v_next]
            dfs(v_next, v, dp_len)
            dp[idx] = past


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

Submission status: Accepted

Solution code:
import sys
import bisect

sys.setrecursionlimit(10**7)
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
printn = lambda x: print(*x, sep='\n')

n = ni()
a = nl()
G = [list() for _ in range(n)]

for _ in range(n-1):
    u, v = nm()
    u -= 1; v -= 1
    G[u].append(v)
    G[v].append(u)

dfsl = list()
seen = [False]*n
stack = [0]
par = [-1]*n
while stack:
    v = stack[-1]
    dfsl.append(v)
    if seen[v]:
        stack.pop()
    else:
        seen[v] = True
        for x in G[v]:
            if x == par[v]:
                continue
            par[x] = v
            stack.append(x)

ans = [0]*n
prv = [0]*n
idx = [None]*n
lis = list()
for v in dfsl:
    if idx[v] is None:
        if not lis or lis[-1] < a[v]:
            idx[v] = len(lis)
            prv[v] = -1
            ans[v] = len(lis) + 1
            lis.append(a[v])
        else:
            i = bisect.bisect_left(lis, a[v])
            idx[v] = i
            prv[v] = lis[i]
            ans[v] = len(lis)
            lis[i] = a[v]
    else:
        if prv[v] < 0:
            lis.pop()
        else:
            lis[idx[v]] = prv[v]
printn(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

sys.setrecursionlimit(230000)
import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur], 0, lis+1)
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [999999999999] * (n+2)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x,dp):
        ans[x] = bisect.bisect_left(dp, float("inf"))
        for y in v[x]:
            if d[y]:
                d[y] = 0
                i = bisect.bisect_left(dp,a[y])
                p = dp[i]
                dp[i] = a[y]
                dfs(y,dp)
                dp[i] = p

    n = I()
    a = LI()
    v = [[] for i in range(n)]
    for _ in range(n-1):
        x,y = LI()
        x -= 1
        y -= 1
        v[x].append(y)
        v[y].append(x)
    dp = [float("inf")]*n
    dp[0] = a[0]
    d = [1]*n
    d[0] = 0
    ans = [0]*n
    dfs(0,dp)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
readline = sys.stdin.readline

def euler_tour(root, Edge):
    N = len(Edge)
    stack = [root]
    used = [False]*N
    tour = []
    down = []
    dist = [0]*N
    ta = tour.append
    sa = stack.append
    St = [None]*N
    En = [None]*N
    cnt = -1
    while stack:
        cnt += 1
        vn = stack.pop()
        ta(vn)
        
        if St[vn] is None:
            St[vn] = cnt
        En[vn] = cnt
        if used[vn]:
            continue
        for vf in Edge[vn]:
            if used[vf]:
                sa(vf)
            else:
                dist[vf] = 1+dist[vn]
                down.append(vf)
        stack.extend(down)
        down = []
        used[vn] = True
    return St, En, tour, dist





N = int(readline())
A = list(map(int, readline().split()))
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)

_, _, L, dist = euler_tour(0, Edge) 

table = [None]*N
table[0] = (-1, -1)
dp = [A[0]]
pre = 0
Ans = [None]*N
for l in L[1:]:
    al = A[l]
    if dist[pre] > dist[l]:
        x, j = table[pre]
        if x == -1:
            dp.pop()
        else:
            dp[j] = x
    else:
        if dp[-1] < al:
            dp.append(al)
            table[l] = (-1, -1)
        else:
            idx = bl(dp, al)
            x = dp[idx]
            dp[idx] = al
            table[l] = (x, idx)
    pre = l
    Ans[l] = len(dp)
        
print('\n'.join(map(str, Ans)))

Submission status: Runtime Error

Solution code:
import bisect
def dfs(i,LIS):
    print(i)
    if a[i] > LIS[-1]:
        LIS.append(a[i])
        ans[i] = len(LIS)
        for j in edges[i]:
            if parent[i] != j:
                parent[j] = i
                dfs(j,LIS)
        LIS.pop()
    else:
        index = bisect.bisect_left(LIS, a[i])
        x = LIS[index]
        LIS[index] = a[i]
        ans[i] = len(LIS)
        for j in edges[i]:
            if parent[i] != j:
                parent[j] = i
                dfs(j,LIS)
        LIS[index] = x

N = int(input())
a = [0]+list(map(int,input().split()))
edges = [[] for _  in range(N+1)]
ans = [-1]*(N+1)
parent = [-1]*(N+1)
for i in range(N-1):
    u,v = map(int,input().split())
    edges[u].append(v)
    edges[v].append(u)
LIS = [a[1]]
dfs(1,LIS)
for i in ans[1:]:
    print(i)

Submission status: Runtime Error

Solution code:
## まきもどし？
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
n = ni()
A = lma()
tree = [[] for i in range(n)]
INF = 10**10
for i in range(n-1):
    u,v = ma();u-=1;v-=1
    tree[u].append(v)
    tree[v].append(u)
#print(tree)
def isok(num,val):##適宜変更
    return num<val
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1,Trueならlen(ls)-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ
def LIS_1(x,ls,right):##right ::これまでわかっている右端
    idx = bisect(ls,x)+1
    if idx+1>right:
        ret= idx+1
    else:
        ret=right
    rewind_idxval.append((idx,ls[idx]))
    ls[idx]=x
    #print(x,ls)
    return ret
def DFS_LIS(prev,ls,right):
    ans[prev]= LIS_1(A[prev],ls,right)
    for node in tree[prev]:
        if not visited[node]:
            visited[node]=True
            DFS_LIS(node,ls,ans[prev])
    #rewind
    idx,pval = rewind_idxval.pop()
    ls[idx] = pval

ans = [0]*n
s = 0
right=0
rewind_idxval=collections.deque()
visited=[False]*n
visited[s]=True
ls=[INF]*n
DFS_LIS(s,ls,right)
#print(ls)
for a in ans :
    print(a)

Submission status: Runtime Error

Solution code:
import math
import bisect

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

tree = [[] for _ in range(n+1)]
parent = [0]+[-1]*(n)
node_used = set()
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])
    parent[uv[1]] = uv[0]
    node_used.add(uv[1])

for i in range(n+1):
    if parent[i] == -1:
        root = i
queue = [root]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        queue.extend(tree[cur])
    else:
        queue.pop()

        #reverse
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1

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

Submission status: Runtime Error

Solution code:
import math
import bisect

n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = map(int,input().split())
    if u > v:
        u,v = v,u
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
node_used = set()
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])
    node_used.add(uv[1])
for i in range(n):
    if not i+1 in node_used:
        root = i+1

queue = [root]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        queue.extend(tree[cur])
    else:
        queue.pop()

        #reverse
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1

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

Submission status: Runtime Error

Solution code:
n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = map(int,input().split())
    if u > v:
        u,v = v,u
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])

queue = [1]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        queue.extend(tree[cur])
    else:
        queue.pop()

        #reverse
        if stack != []:
            back = stack.pop()
            if back[1] == None:
                dp.pop()
            else:
                dp[back[0]] = back[1]
    used[cur] = 1

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

Submission status: Runtime Error

Solution code:
n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = map(int,input().split())
    if u > v:
        u,v = v,u
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])

queue = [1]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        queue.extend(tree[cur])
    else:
        queue.pop()

        #reverse
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1

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

Submission status: Runtime Error

Solution code:
n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = map(int,input().split())
    if u > v:
        u,v = v,u
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])

queue = [1]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        queue.extend(tree[cur])
    else:
        queue.pop()

        #reverse
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
from collections import deque
import sys

sys.setrecursionlimit(20000)

N = int(input())

a = list(map(int,input().split()))

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

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

INF = 10**11
ans = [0]*N
dp = []###INFは空欄として扱って良い
stack = deque([])

def LISonTree(num,pre):
    ###num: 頂点番号
    ###pre: 1つ前にいた頂点番号
    p = bisect_left(dp,a[num])

    ###
    #print(p)
    ###

    if p >= len(dp):
        stack.appendleft((len(dp),INF))
        dp.append(a[num])
    else:
        stack.appendleft((p,dp[p]))
        dp[p] = a[num]
    
    q = bisect_left(dp,INF)
    ans[num] = q

    ###
    #print(num,'dp',dp)
    #print(num,'ans',ans)
    ###

    for x in graph[num]:
        if x == pre:
            continue
        LISonTree(x,num)
    
    changed_p, changed_v = stack.popleft()

    dp[changed_p] = changed_v

    ###
    #print(num,'dp',dp)
    ###

LISonTree(0,-1)
#print(ans)

for y in ans:
    print(y)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
from collections import deque
import sys

sys.setrecursionlimit(10000)

N = int(input())

a = list(map(int,input().split()))

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

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

INF = 10**11
ans = [0]*N
dp = []###INFは空欄として扱って良い
stack = deque([])

def LISonTree(num,pre):
    ###num: 頂点番号
    ###pre: 1つ前にいた頂点番号
    p = bisect_left(dp,a[num])

    ###
    #print(p)
    ###

    if p >= len(dp):
        stack.appendleft((len(dp),INF))
        dp.append(a[num])
    else:
        stack.appendleft((p,dp[p]))
        dp[p] = a[num]
    
    q = bisect_left(dp,INF)
    ans[num] = q

    ###
    #print(num,'dp',dp)
    #print(num,'ans',ans)
    ###

    for x in graph[num]:
        if x == pre:
            continue
        LISonTree(x,num)
    
    changed_p, changed_v = stack.popleft()

    dp[changed_p] = changed_v

    ###
    #print(num,'dp',dp)
    ###

LISonTree(0,-1)
#print(ans)

for y in ans:
    print(y)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
from collections import deque

N = int(input())

a = list(map(int,input().split()))

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

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

INF = 10**11
ans = [0]*N
dp = []###INFは空欄として扱って良い
stack = deque([])

def LISonTree(num,pre):
    ###num: 頂点番号
    ###pre: 1つ前にいた頂点番号
    p = bisect_left(dp,a[num])

    ###
    #print(p)
    ###

    if p >= len(dp):
        stack.appendleft((len(dp),INF))
        dp.append(a[num])
    else:
        stack.appendleft((p,dp[p]))
        dp[p] = a[num]
    
    q = bisect_left(dp,INF)
    ans[num] = q

    ###
    #print(num,'dp',dp)
    #print(num,'ans',ans)
    ###

    for x in graph[num]:
        if x == pre:
            continue
        LISonTree(x,num)
    
    changed_p, changed_v = stack.popleft()

    dp[changed_p] = changed_v

    ###
    #print(num,'dp',dp)
    ###

LISonTree(0,-1)
#print(ans)

for y in ans:
    print(y)

Submission status: Runtime Error

Solution code:
def binary_search(c1, c2, x):
    m = (c1 + c2 + 1) // 2
    if abs(c1 - c2) <= 1:
        return m
    else:
        if dp[m] >= x:
            c1 = m
        else:
            c2 = m
        return binary_search(c1, c2, x)

def dfs(i, dp, cnt):
    ans[i] = cnt
    for j in G[i]:
        if ans[j] == -1:
            m = binary_search(n + 4, -1, a[j])
            k = dp[m]
            dp[m] = a[j]
            dfs(j, dp, max(cnt, m + 1))
            dp[m] = k
    return

n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
inf = 1145141919
dp = [inf for _ in range(n + 5)]
ans = [-1] * (n + 1)
m = binary_search(n - 1, -1, a[1])
dp[m] = a[1]
ans[1] = 1
dfs(1, dp, 1)
for i in range(1, n + 1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
def binary_search(c1, c2, x):
    m = (c1 + c2 + 1) // 2
    if abs(c1 - c2) <= 1:
        return m
    else:
        if dp[m] >= x:
            c1 = m
        else:
            c2 = m
        return binary_search(c1, c2, x)

def dfs(i, dp, cnt):
    ans[i] = cnt
    for j in G[i]:
        if ans[j] == -1:
            m = binary_search(n - 1, -1, a[j])
            k = dp[m]
            dp[m] = a[j]
            dfs(j, dp, max(cnt, m + 1))
            dp[m] = k
    return

n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
inf = 1145141919
dp = [inf for _ in range(n)]
ans = [-1] * (n + 1)
m = binary_search(n - 1, -1, a[1])
dp[m] = a[1]
ans[1] = 1
dfs(1, dp, 1)
for i in range(1, n + 1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
UV=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
for i,j in UV:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
v=[0]*N
d=[10**9+1]*N
stk=[]
ans=[0]*N
from bisect import bisect_left
def dfs(p,l):
    i=bisect_left(d,A[p])
    stk.append((i,d[i]))
    d[i]=A[p]
    if i==l:
        l+=1
    ans[p]=l
    for n in c[p]:
        if v[n]==0:
            v[n]=1
            dfs(n,l)
    i,x=stk.pop()
    d[i]=x
v[0]=1
dfs(0,0)
print(*ans,sep='\n')