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: Runtime Error

Solution code:
from collections import deque
import bisect


N = int(input())
a = list(map(int, input().split()))
uvs = [list(map(int, input().split())) for _ in range(N-1)]
shortest = [10e+10 for _ in range(N)]
shortest[0] = 0

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

for uv in uvs:
    routes[uv[0]-1].append(uv[1]-1)
    routes[uv[1]-1].append(uv[0]-1)

lis = [10e+100 for _ in range(N)]
minimum = [10e+100 for _ in range(N)]
seen = [False for _ in range(N)]
seen[0] = True

def function(checking):
    insert_posi = bisect.bisect_left(lis, a[checking])
    preserved = lis[insert_posi]
    lis[insert_posi] = a[checking]
    minimum[checking] = bisect.bisect_left(lis, 10e+50)
    for route in routes[checking]:
        if seen[route] == False:
            seen[route] = True
            shortest[route] = shortest[checking]+1
            function(route)
    lis[insert_posi] = preserved
    return
        
function(0)

minimum = [[minimum[i],shortest[i]] for i in range(N)]

minimum = sorted(minimum, key=lambda x:x[1])

[print(x[0]) for x in minimum]

Submission status: Runtime Error

Solution code:
#F
import bisect

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

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

DP = [inf]*(N+1)
stack = []
ans = [-1]*N
seen = [False]*N

#DFS
def dfs(gragh, v): #v = start
    """
    global A
    global DP
    global ans
    global stack 
    global seen
    """
    
    seen[v] = True
    ind = bisect.bisect_left(DP,A[v])
    mae = DP[ind]
    DP[ind] = A[v]
    stack.append([ind,mae])
    
    ans[v] = bisect.bisect_left(DP,inf)
    
    for next_v in gragh[v]:
        if seen[next_v]: 
            continue
        
        dfs(gragh,next_v)
        
    ind,mae = stack.pop()
    DP[ind] = mae
    
    return



dfs(on,0)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
#F
from collections import deque
import bisect

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

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

DP = [inf]*N
stack = []
ans = [-1]*N
seen = [False]*N

#DFS
def dfs(gragh, v): #v = start
    global A
    global DP
    global ans
    global stack 
    global seen
    
    seen[v] = True
    ind = bisect.bisect_left(DP,A[v])
    mae = DP[ind]
    DP[ind] = A[v]
    stack.append([ind,mae])
    
    ans[v] = bisect.bisect_left(DP,inf)
    
    for next_v in gragh[v]:
        if seen[next_v]: 
            continue
        
        dfs(gragh,next_v)
        
    ind,mae = stack.pop()
    DP[ind] = mae
    
    return



dfs(on,0)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


from bisect import bisect_left, bisect_right, insort_left


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html
        ls ... 渡す初期配列
        '''
        self.bst = ls  # insertをO(1)にするためにlistの代わりにdequeを用います

    def __repr__(self):
        return f'BST:{self.bst}'

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        insort_left(self.bst, x)

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) + 1
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd

# 各ノードに今までの最長増加部分列と現在の増加部分列長の記録があれば、たかだた分岐地点から探索できるのでは？
N = read_a_int()
A = read_ints()
Tree = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = read_ints()
    u -= 1
    v -= 1
    Tree[u].append(v)
    Tree[v].append(u)

LIS = BinarySearchTree([-1])

ans = [-1] * N


@njit
def dfs(u, p, LIS):  # これって参照渡しに成るんすかねすると厄介かもしれない
    '''現在のノード、親、最長増加部分列の状態'''
    LIS.insert_replace_right(A[u])
    ans[u] = len(LIS) - 1
    # print(u, LIS.bst)
    if len(Tree[u]) > 2 or u == 0:  # 配列のコピーを渡す
        for nu in Tree[u]:
            if nu == p:
                continue
            dfs(nu, u, BinarySearchTree(LIS.bst.copy()))  # ここでTLE
    elif len(Tree[u]) == 2:  # 参照渡しでok
        for nu in Tree[u]:
            if nu == p:
                continue
            dfs(nu, u, LIS)


# def dfs(u, p, LIS):  # これって参照渡しに成るんすかねすると厄介かもしれない
#     '''現在のノード、親、最長増加部分列の状態'''
#     LIS.insert_replace_right(A[u])
#     ans[u] = len(LIS) - 1
#     for nu in Tree[u]:
#         if nu == p:
#             continue
#         dfs(nu, u, BinarySearchTree(LIS.bst.copy()))


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

Submission status: Runtime Error

Solution code:
from collections import deque
import bisect
import sys


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

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

for uv in uvs:
    routes[uv[0]-1].append(uv[1]-1)

lis = [10e+100 for _ in range(N)]
shortest = [10e+100 for _ in range(N)]
shortest[0] = 0
minimum = [10e+100 for _ in range(N)]
seen = [False for _ in range(N)]
seen[0] = True

def function(checking):
    insert_posi = bisect.bisect_left(lis, a[checking])
    preserved = lis[insert_posi]
    lis[insert_posi] = a[checking]
    minimum[checking] = bisect.bisect_left(lis, 10e+50)
    for route in routes[checking]:
        if seen[route] == False:
            shortest[route] = shortest[checking]+1
            seen[route] = True
            function(route) 
    lis[insert_posi] = preserved
    return
        
function(0)

[print(i) for i in (minimum)]

Submission status: Runtime Error

Solution code:
from collections import deque
import bisect
import sys


N = int(input())
a = list(map(int, f.input().split()))
uvs = [list(map(int, input().split())) for _ in range(N-1)]

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

for uv in uvs:
    routes[uv[0]-1].append(uv[1]-1)
    routes[uv[1]-1].append(uv[0]-1)

lis = [10e+100 for _ in range(N)]
shortest = [10e+100 for _ in range(N)]
shortest[0] = 0
minimum = [10e+100 for _ in range(N)]
seen = [False for _ in range(N)]
seen[0] = True

def function(checking):
    insert_posi = bisect.bisect_left(lis, a[checking])
    preserved = lis[insert_posi]
    lis[insert_posi] = a[checking]
    minimum[checking] = bisect.bisect_left(lis, 10e+50)
    for route in routes[checking]:
        if seen[route] == False:
            shortest[route] = shortest[checking]+1
            seen[route] = True
            function(route) 
    lis[insert_posi] = preserved
    return
        
function(0)

[print(i) for i in (minimum)]

Submission status: Runtime Error

Solution code:
from collections import deque
import bisect
import sys


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

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

for uv in uvs:
    routes[uv[0]-1].append(uv[1]-1)
    routes[uv[1]-1].append(uv[0]-1)

lis = [10e+100 for _ in range(N)]
shortest = [10e+100 for _ in range(N)]
shortest[0] = 0
minimum = [10e+100 for _ in range(N)]
seen = [False for _ in range(N)]
seen[0] = True

def function(checking):
    insert_posi = bisect.bisect_left(lis, a[checking])
    preserved = lis[insert_posi]
    lis[insert_posi] = a[checking]
    minimum[checking] = bisect.bisect_left(lis, 10e+50)
    print(minimum[checking])
    for route in routes[checking]:
        if seen[route] == False:
            shortest[route] = shortest[checking]+1
            seen[route] = True
            function(route) 
    lis[insert_posi] = preserved# callback
    return
        
function(0)

Submission status: Runtime Error

Solution code:
import sys
import copy
import bisect

sys.setrecursionlimit(202020)

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

ans = [1 for _ in range(N)]

def dfs(u, p, L, length):
    print(u)
    ans[u] = length
    for v in to[u]:
        if v == p:
            continue
        L_copy = copy.deepcopy(L)
        if L[-1] < a[v]:
            L_copy.append(a[v])
            dfs(v, u, L_copy, length+1)
        else:
            p = bisect.bisect_left(L_copy, a[v])
            L_copy[p] = a[v]
            dfs(v, u, L_copy, length)

dfs(0, -1, [a[0]], 1)
for i in range(N):
    print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from itertools import combinations_with_replacement, combinations
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = LI()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


ans = [0] * n
depth = [0] * n
def euler_tour():
    euler = []
    dq = deque([0])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [u]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                dq += [v]
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                depth[v] = depth[u] + 1
                dq2 += [v]
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return euler


order = euler_tour()

P = [0] * n
LIS = [A[0]]
pre = -1
ret = 1
for i in order:
    if depth[i] > pre:
        if A[i] > LIS[-1]:
            LIS += [A[i]]
            ret += 1
            P[i] = (-1, 0)
        else:
            idx = bisect_left(LIS, A[i])
            P[i] = (idx, LIS[idx])
            LIS[idx] = A[i]
        ans[i] = ret
    else:
        idx, e = P[i]
        if idx == -1:
            LIS.pop()
            ret -= 1
        else:
            LIS[idx] = e
    pre = depth[i]

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

Submission status: Runtime Error

Solution code:
from bisect import bisect

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 = 10 ** 9 + 7
dp = [INF] * (N + 1)
dp[0] = -INF
ans = [0] * N

def dfs(u, p=-1):
    # Update dp
    i = bisect(dp, A[u])
    old = dp[i]
    dp[i] = A[u]

    # Calc ans
    ans[u] = i
    if p != -1:
        ans[u] = max(ans[u], ans[p])

    # Go to next
    for v in graph[u]:
        if v == p:
            continue
        dfs(v, u)

    # Restore
    dp[i] = old

dfs(0)
print(*ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect

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 = 10 ** 9 + 7
dp = [INF] * N
dp[0] = -INF
ans = [0] * N

def dfs(u, p=-1):
    # Update dp
    i = bisect(dp, A[u])
    old = dp[i]
    dp[i] = A[u]

    # Calc ans
    ans[u] = i
    if p != -1:
        ans[u] = max(ans[u], ans[p])

    # Go to next
    for v in graph[u]:
        if v == p:
            continue
        dfs(v, u)

    # Restore
    dp[i] = old

dfs(0)
print(*ans)

Submission status: Runtime Error

Solution code:
def LIS(L,n):
  res=0
  dp=[1]*n
  for i in range(n):
    for j in range(i):
      if L[j]<L[i]:
        dp[i]=max(dp[i],dp[j]+1)
    res=max(res,dp[i])
  return res
  
def setParent(c,parent):
    if parent[c]!=float('inf'):
        setParent(parent[c],parent)
        parent[parent[c]]=c
 
n=int(input())
a=list(map(int,input().split()))
parent=[float('inf')]*n
root=[[] for i in range(n)]

for i in range(n-1):
    l=list(map(int,input().split()))
    if parent[l[1]-1]==float('inf'):
        parent[l[1]-1]=l[0]-1
    elif parent[l[0]-1]==float('inf'):
        parent[l[0]-1]=l[1]-1
    else:
        setParent(l[1]-1,parent)
        parent[l[1]-1]=l[0]-1
        
setParent(0,parent)
parent[0]=float('inf')
    
for i in range(1,n):
    c=parent[i]
    root[i].append(a[i])
    while(c!=0):
        if not root[c]:
            root[i].extend([a[c]])
            c=parent[c]
        else:
            root[i].extend(root[c])
            break

print(1)
for i in range(1,n):
    root[i].extend([a[0]])
    root[i].reverse()
    res=LIS(root[i],len(root[i]))
    print(res)

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline
import bisect
from collections import deque
from copy import deepcopy

n = int(input())
l = list(map(int,input().split()))
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)


ans = [0]*n
ans[0] = 1
dp = [l[0]]
q = deque([])
q.append((0,-1,-1))

def dfs(now,bef):
    
    change = True
    if l[now] > dp[-1]:
        dp.append(l[now])
    else:
        index = bisect.bisect_left(dp,l[now])
        change = False
        s = dp[index]
        dp[index] = l[now] 
    ans[now] = len(dp)
    
    for nex in e[now]:
        if nex != bef:
            dfs(nex,now)
    if change:
        dp.pop()
    else:
        dp[index] = s 

for i in e[0]:
    dfs(i,0)

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
def LIS(L,n):
  res=0
  dp=[1]*n
  for i in range(n):
    for j in range(i):
      if L[j]<L[i]:
        dp[i]=max(dp[i],dp[j]+1)
    res=max(res,dp[i])
  return res
  
def setParent(c,parent):
    if parent[c]!=float('inf'):
        setParent(parent[c],parent)
        parent[parent[c]]=c
 
n=int(input())
a=list(map(int,input().split()))
parent=[float('inf')]*n
root=[[a[i]] for i in range(n)]

for i in range(n-1):
    l=list(map(int,input().split()))
    if parent[l[1]-1]==float('inf'):
        parent[l[1]-1]=l[0]-1
    elif parent[l[0]-1]==float('inf'):
        parent[l[0]-1]=l[1]-1
    else:
        setParent(l[1]-1,parent)
        parent[l[1]-1]=l[0]-1
        
setParent(0,parent)
parent[0]=float('inf')
    
for i in range(1,n):
    c=parent[i]
    while(c!=0):
        if not root[c]:
            root[i].extend([a[c]])
            c=parent[c]
        else:
            root[i].extend(root[c])
            break

print(1)
for i in range(1,n):
    root[i].extend([1])
    root[i].reverse()
    res=LIS(root[i],len(root[i]))
    print(res)

Submission status: Runtime Error

Solution code:
def LIS(L,n):
  res=0
  dp=[1]*n
  for i in range(n):
    for j in range(i):
      if L[j]<L[i]:
        dp[i]=max(dp[i],dp[j]+1)
    res=max(res,dp[i])
  return res
  
def setParent(c,parent):
    if parent[c]!=float('inf'):
        setParent(parent[c],parent)
        parent[parent[c]]=c
 
n=int(input())
a=list(map(int,input().split()))
parent=[float('inf')]*n
root=[[a[i]] for i in range(n)]

for i in range(n-1):
    l=list(map(int,input().split()))
    if parent[l[1]-1]==float('inf'):
        parent[l[1]-1]=l[0]-1
    else:
        parent[l[0]-1]=l[1]-1
        
setParent(0,parent)
parent[0]=float('inf')
    
for i in range(1,n):
    c=parent[i]
    while(c!=float('inf')):
        if not root[c]:
            root[i].extend([a[c]])
            c=parent[c]
        else:
            root[i].extend(root[c])
            break

print(1)
for i in range(1,n):
    root[i].extend([1])
    root[i].reverse()
    res=LIS(root[i],len(root[i]))
    print(res)

Submission status: Runtime Error

Solution code:
def LIS(L,n):
  res=0
  dp=[1]*n
  for i in range(n):
    for j in range(i):
      if L[j]<L[i]:
        dp[i]=max(dp[i],dp[j]+1)
    res=max(res,dp[i])
  return res
  
def setParent(c,parent):
    if parent[c]!=float('inf'):
        setParent(parent[c],parent)
        parent[parent[c]]=c
 
n=int(input())
a=list(map(int,input().split()))
parent=[float('inf')]*n
root=[[a[i]] for i in range(n)]

for i in range(n-1):
    l=list(map(int,input().split()))
    if parent[l[1]-1]==float('inf'):
        parent[l[1]-1]=l[0]-1
    else:
        parent[l[0]-1]=l[1]-1
        
setParent(0,parent)
parent[0]=float('inf')
    
for i in range(1,n):
    c=parent[i]
    while(c!=0):
        if not root[c]:
            root[i].extend([a[c]])
            c=parent[c]
        else:
            root[i].extend(root[c])
            break

print(1)
for i in range(1,n):
    root[i].extend([1])
    root[i].reverse()
    res=LIS(root[i],len(root[i]))
    print(res)

Submission status: Runtime Error

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

N = int(input())
A = list(map(int, input().split()))
dp = [float('inf')] * (N + 1)
ans = [0] * N

def dfs(s,edge):
    global ans, dp
    index = bisect.bisect_left(dp[s], A[s])
    old = dp[index]
    length = bisect.bisect_left(dp[s], float('inf'))
    ans[index] = length
    for i in edge[s]:
        if i == s:
            continue
        dfs(i,edge)
    dp[index] = old

def main():
    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)

    dfs(0,edge)
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        repn[u - 1].append(v - 1)
        repn[v - 1].append(u - 1)
    
    length = [0] * (N + 1)
    dp = [-1]

    """
    やはり各頂点でLIS配列を取ると配列コピーの時間がかかってTLEするので、
    配列は唯一つを扱って、DFSからバックするときに配列も元に戻す操作を行いたい
    （ここの実装の仕方がわからなかった）

    これはdfsを再帰で書いた後に復元操作を追記すれば異常に楽に書ける。。。
    """

    def dfs(v, p=N):
        if A[v] > dp[-1]:
            dp.append(A[v])
            length[v] = length[p] + 1
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp.pop()
        else:
            idx = bisect_right(dp, A[v])
            old = dp[idx]
            dp[idx] = A[v]
            length[v] = length[p]
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
                dp[idx] = old
        #print("v={}, len={}, dp={}".format(v, length[v], dp))

    dfs(0)
    length.pop()
    for ans in length:
        print(ans)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

N = int(input())
A = tuple(map(int, input().split()))
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

ans = [-1] * (N + 1)
inf = 10**8
LIS = [inf] * (N + 10)


def DFS(s, parent=0):
    a = A[s - 1]
    i = bisect.bisect_left(LIS, a)
    v = LIS[i]
    LIS[i] = a
    ans[s] = bisect.bisect_left(LIS, inf)
    for t in edge[s]:
        if t == parent:
            continue
        DFS(t, s)
    # 頂点sでの結果をもとに戻す
    LIS[i] = v
    return


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

Submission status: Runtime Error

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

N = int(input())
A = tuple(map(int, input().split()))
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

ans = [-1] * (N + 1)
inf = 10**8
LIS = [inf] * (N + 1)


def DFS(s, parent=0):
    a = A[s - 1]
    i = bisect.bisect_left(LIS, a)
    v = LIS[i]
    LIS[i] = a
    ans[s] = bisect.bisect_left(LIS, inf)
    for t in edge[s]:
        if t == parent:
            continue
        DFS(t, s)
    # 頂点sでの結果をもとに戻す
    LIS[i] = v
    return


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

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import numpy as np
import copy
import bisect

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

arrive = [False] * (N+1)
dp_dict = np.array([None] * N)
dp_dict[0] = [A[0]]


ans = [None] *(N+1)
def dfs(s):
    stack = deque([s])
    while stack:
        v = stack[-1]
        arrive[v] = True
        if graph[v]:
            w = graph[v].pop()
            if arrive[w] == False:
                tar = A[w-1]
                dp = dp_dict[v-1].copy()
                if tar > dp[-1]:
                    dp.append(tar)
                else:
                    dp[bisect.bisect_left(dp, tar)] = tar
                ans[w] = len(dp)
                dp_dict[w-1] = dp
                stack.append(w)

        else:
            stack.pop()


dfs(1)
ans[1] = 1
for i in ans[1::]:
    print(i)

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import numpy as np
import copy
import bisect

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

arrive = [False] * (N+1)
dp_dict = np.array([None] * N)
dp_dict[0] = [A[0]]


ans = [None] *(N+1)
def dfs(s):
    stack = deque([s])
    while stack:
        v = stack[-1]
        arrive[v] = True
        if graph[v]:
            w = graph[v].pop()
            if arrive[w] == False:
                tar = A[w-1]
                dp = dp_dict[v].copy()
                if tar > dp[-1]:
                    dp.append(tar)
                else:
                    dp[bisect.bisect_left(dp, tar)] = tar
                ans[w] = len(dp)
                dp_dict[w-1] = dp
                stack.append(w)

        else:
            stack.pop()


dfs(1)
ans[1] = 1
for i in ans[1::]:
    print(i)

Submission status: Runtime Error

Solution code:
#include "bits/stdc++.h"

using namespace std;

#define cerr if(false)cerr
#define what(x) cerr<<#x<<" = "<<x<<endl
 
typedef long long ll;
typedef pair<ll, ll> ii;

const int maxN = 3e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 322;
const int INF = 1e9 + 10;


vector<int> LIS(maxN, INF);
vector<int> adj[maxN];
vector<int> arr(maxN);
vector<int> ans(maxN, 0);

void DFS(int node, int parent = -1){
	
	//TRATAR DE MODIFICARLO
	int indx = upper_bound(LIS.begin(), LIS.end(), arr[node]) - LIS.begin();
	int ant = LIS[indx];
	if(LIS[indx-1] < arr[node] && arr[node] < LIS[indx]){
		LIS[indx] = arr[node];
	}


	//Encontrar respuesta
	int siz = lower_bound(LIS.begin(), LIS.end(), INF) - LIS.begin();
	ans[node] = siz - 1;

	//Propagar
	for(auto& it : adj[node]){
		if(it == parent)continue;
		DFS(it, node);
	}

	//REGRESAR
	LIS[indx] = ant;
}

int main(){

	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	int a, b;
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}

	for(int i = 0; i < n-1; i++){
		cin >> a >> b;
		--a;--b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	LIS[0] = -INF;

	//DFS(0);
	for(int i = 0; i < n; i++){
		cout << ans[i] << endl;
	}

	return 0;
}

Submission status: Runtime Error

Solution code:
#include "bits/stdc++.h"

using namespace std;

#define cerr if(false)cerr
#define what(x) cerr<<#x<<" = "<<x<<endl
 
typedef long long ll;
typedef pair<ll, ll> ii;

const int maxN = 3e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 322;
const int INF = 1e9 + 10;


vector<int> LIS(maxN, INF);
vector<int> adj[maxN];
vector<int> arr(maxN);
vector<int> ans(maxN, 0);

void DFS(int node, int parent = -1){
	
	//TRATAR DE MODIFICARLO
	int indx = upper_bound(LIS.begin(), LIS.end(), arr[node]) - LIS.begin();
	int ant = LIS[indx];
	if(LIS[indx-1] < arr[node] && arr[node] < LIS[indx]){
		LIS[indx] = arr[node];
	}


	//Encontrar respuesta
	int siz = lower_bound(LIS.begin(), LIS.end(), INF) - LIS.begin();
	ans[node] = siz - 1;

	//Propagar
	for(auto& it : adj[node]){
		if(it == parent)continue;
		DFS(it, node);
	}

	//REGRESAR
	LIS[indx] = ant;
}

int main(){

	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	int a, b;
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}

	for(int i = 0; i < n-1; i++){
		cin >> a >> b;
		--a;--b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	LIS[0] = -INF;

	DFS(0);
	for(int i = 0; i < n; i++){
		cout << ans[i] << endl;
	}

	return 0;
}

Submission status: Runtime Error

Solution code:
#include "bits/stdc++.h"

using namespace std;

#define cerr if(false)cerr
#define what(x) cerr<<#x<<" = "<<x<<endl
 
typedef long long ll;
typedef pair<ll, ll> ii;

const int maxN = 2e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 322;
const int INF = 1e9 + 10;


vector<int> LIS(maxN, INF);
vector<int> adj[maxN];
vector<int> arr(maxN);
vector<int> ans(maxN, 0);

void DFS(int node, int parent = -1){
	
	//TRATAR DE MODIFICARLO
	int indx = upper_bound(LIS.begin(), LIS.end(), arr[node]) - LIS.begin();
	int ant = LIS[indx];
	if(LIS[indx-1] < arr[node] && arr[node] < LIS[indx]){
		LIS[indx] = arr[node];
	}


	//Encontrar respuesta
	int siz = lower_bound(LIS.begin(), LIS.end(), INF) - LIS.begin();
	ans[node] = siz - 1;

	//Propagar
	for(auto& it : adj[node]){
		if(it == parent)continue;
		DFS(it, node);
	}

	//REGRESAR
	LIS[indx] = ant;
}

int main(){

	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	int a, b;
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}

	for(int i = 0; i < n-1; i++){
		cin >> a >> b;
		--a;--b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	LIS[0] = -INF;

	DFS(0);
	for(int i = 0; i < n; i++){
		cout << ans[i] << endl;
	}

	return 0;
}

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import bisect
from copy import deepcopy

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

arrive = [False] * (N+1)
dp_dict = dict()
dp_dict[1] = [A[0]]

ans = [None] *(N+1)
def dfs(s):
    stack = deque([s])
    while stack:
        v = stack[-1]
        arrive[v] = True
        if graph[v]:
            w = graph[v].popleft()
            if arrive[w] == False:
                tar = A[w-1]
                dp = deepcopy(dp_dict[v])
                if tar > dp[-1]:
                    dp.append(tar)
                else:
                    dp[bisect.bisect_left(dp, tar)] = tar
                ans[w] = len(dp)
                dp_dict[w] = dp
                dfs(w)

        else:
            stack.pop()


dfs(1)
ans[1] = 1

for i in ans[1::]:
    print(i)