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:
def resolve():
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    import numpy as np
    n = int(input())
    a = list(map(int, input().split()))
    edge = np.array([input().split() for _ in range(n - 1)], dtype=np.int64).T
    b = csr_matrix(([1] * (n - 1), (edge - 1)), shape=(n, n)).toarray()
    s, p = shortest_path(b, directed=False, indices=0,
                         return_predecessors=True)
    ans = 0
    for i in range(1, n):
        r = [a[x] for x in get_path_row(0, i, p)]
        print(getlength(r))


def getlength(L):
    res = 0
    N = len(L)
    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 get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import bisect

def lis(lst):
    lis_lst = [lst[0]]
    for i in lst:
        if i > lis_lst[-1]:
            lis_lst.append(i)
        else:
            lis_lst[bisect.bisect_left(lis_lst, i)] = i
    return len(lis_lst)

n = int(input())

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

uv = {}
for _ in range(n-1):
    u, v = map(int, input().split())
    uv[v] = u
    
for i in range(1, n + 1):
    lst = []    
    while i != 1:
        lst.append(a[i - 1])
        i = uv[i]
    lst.append(a[i- 1])
    lst.reverse()
    print(lis(lst))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
g = [[]for _ in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)
import copy
import queue
import bisect
check = [False]*n
check[0] = True
li = [a[0]]
import collections
q= collections.deque()
q.append([0,li])
ans = [0]*n
ans[0] = 1
while q:
    now,lisOrigin= q.popleft()
    for ne in g[now]:
        if check[ne]:
            continue
        check[ne] = True
        lis = copy.deepcopy(lisOrigin)
        if a[ne] > lis[-1]:
            lis.append(a[ne])
        else:
            lis[bisect.bisect_left(lis,a[ne])] = a[ne]
        q.append([ne,lis])
        ans[ne] = len(lis)n=int(input())
a=list(map(int,input().split()))
g = [[]for _ in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)
import copy
import queue
import bisect
check = [False]*n
check[0] = True
li = [a[0]]
import collections
q= collections.deque()
q.append([0,li])
ans = [0]*n
ans[0] = 1
while q:
    now,lisOrigin= q.popleft()
    for ne in g[now]:
        if check[ne]:
            continue
        check[ne] = True
        lis = copy.deepcopy(lisOrigin)
        if a[ne] > lis[-1]:
            lis.append(a[ne])
        else:
            lis[bisect.bisect_left(lis,a[ne])] = a[ne]
        q.append([ne,lis])
        ans[ne] = len(lis)

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

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

Submission status: Runtime Error

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


def inp():
    return int(input())


def dfs(s, b, lis, ansl, lines, aa):
    a = aa[s]
    idx = bisect.bisect_left(lis, a)

    if len(lis) == idx:
        lis.append(a)
    else:
        lis[idx] = a

    ansl[s] = len(lis)

    if len(lines[s]) >= 3:
        for t in lines[s]:
            if t != b:
                dfs(t, s, lis.copy(), ansl, lines, aa)
    else:
        for t in lines[s]:
            if t != b:
                dfs(t, s, lis, ansl, lines, aa)


def main():
    N = inp()
    aa = map(int, input().split())

    lines = [[] for _ in range(N)]
    for _ in range(N - 1):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        lines[s].append(t)
        lines[t].append(s)

    lines[0].append(-1)

    ansl = [0] * N

    dfs(0, -1, [], ansl, lines, aa)

    print("\n".join(map(str, ansl)))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import bisect

def lis(lst):
    lis_lst = [lst[0]]
    for i in lst:
        if i > lis_lst[-1]:
            lis_lst.append(i)
        else:
            lis_lst[bisect.bisect_left(lis_lst, i)] = i
    return len(lis_lst)

n = int(input())

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

uv = {}
for _ in range(n-1):
    u, v = map(int, input().split())
    uv[v] = u
    
for i in range(1, n + 1):
    lst = []    
    while i != 1:
        lst.append(a[i - 1])
        i = uv[i]
    lst.append(a[i- 1])
    lst.reverse()
    print(lis(lst))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(n - 1)]

import sys #追加
sys.setrecursionlimit(10 ** 7) #追加

from collections import defaultdict
g = defaultdict(list)
for i in range(n - 1):
    u = uv[i][0] - 1
    v = uv[i][1] - 1
    g[u].append(v)
    g[v].append(u)

from bisect import bisect_left
ans = [0] * n
visited = [0] * n

def dfs(cur, dp):
    visited[cur] = 1
    idx = bisect_left(dp, a[cur])
    #print(cur, dp, idx)

    if idx == len(dp):
        dp.append(a[cur])
        ans[cur] = len(dp)
        for target in g[cur]:
            if visited[target] == 0:
                dfs(target, dp)
                dp.pop()

    else:
        old = dp[idx]
        dp[idx] = a[cur]
        ans[cur] = len(dp)
        for target in g[cur]:
            if visited[target] == 0:
                dfs(target, dp)
                dp[idx] = old

dfs(0, [])

for _ans in ans:
    print(_ans)

Submission status: Runtime Error

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())

a = lmi()

adj = collections.defaultdict(set)
uv = llmi(N - 1)
for _u, _v in uv:
    u, v = _u - 1, _v - 1
    adj[u].add(v)
    adj[v].add(u)

trees = {}


class Tree:
    def __init__(self, index, parent_index=None):
        self.val = a[index]
        self.index = index
        self.parent = parent_index
        self.adj = []
        for v in adj[index]:
            if v == parent_index:
                continue
            self.adj.append(Tree(v, parent_index=self.index))
        self.ans = None
        trees[index] = self

    def __repr__(self):
        return '{}: {}'.format(self.index, [t.val for t in self.adj])

    def dp(self, current=None, diffs=[]):
        if current is None:
            current = []
        # print(current, diffs)
        v = bisect.bisect_left(current, self.val)
        # print(current)
        if v >= len(current):
            diffs.append((v, None))
            current.append(self.val)
        else:
            diffs.append((v, current[v]))
            current[v] = self.val
        # old_current = list(current)
        self.ans = len(current)
        for child_tree in self.adj:
            diffs = child_tree.dp(current, diffs)
            index, val = diffs.pop()
            if val is None:
                current.pop()
            else:
                current[index] = val
            # print(old_current, current, index, val)
        return diffs


root = Tree(0)
root.dp()
for i in range(N):
    print(trees[i].ans)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import bisect

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [[float("inf"),[a[s]]] for i in range(n)]
    used = [False] * n
    d[s][0] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i][0] < d[v][0]:
                v = i
        if v == -1:
                break
        used[v] = True
               
        for j in range(n):
            d[j][0] = min(d[j][0],d[v][0]+cost[v][j])
            if d[j][0] < d[v][0]+cost[v][j]:
                continue
            d[j][1] = d[v][1]
            if a[v] > d[j][1][-1]:
                d[j][1].append(a[v])
            else:
                d[j][1][bisect.bisect_left(d[v][1], a[j])] = a[v]
    return d

################################
n = ni()
a = na()

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(n-1):
    x,y = na()
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1

d = dijkstra(0,n,n-1,cost)

for i in range(n):
    print(len(d[i][1]))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        x,y=map(int1,input().split())
        edge[x].append(y)
        edge[y].append(x)
    stack=[(0,1)]
    dp=[INF]*(N+10)
    dp[0]=0
    used=[False]*N
    ans=[0]*N
    while stack:
        v,l=stack.pop()
        used[v]=True
        dp[l:]=[INF]*(N-l)
        dp[bisect_right(dp,a[v]-1,hi=l)]=a[v]
        ans[v]=bisect_left(dp,INF,hi=l+1)-1
        for nv in edge[v]:
            if not used[nv]:
                stack.append((nv,l+1))
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
A=list(map(int,input().split()))

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

B=[1]*n
temp=[1]*n
ongoing=[1]*n
queue = deque([0])
visited= [0]*n
while queue:
    a = queue.popleft()
    visited[0] = 1
    for i in G[a]:
        if visited[i] == 0:
            if A[i]>A[a]:
                ongoing[i]=ongoing[a]+1
            temp[i]=max(temp[a],ongoing[i])
            visited[a] = 1
            queue.append(i)    

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        x,y=map(int1,input().split())
        edge[x].append(y)
        edge[y].append(x)
    stack=[(0,1)]
    dp=[INF]*N
    dp[0]=0
    used=[False]*N
    ans=[0]*N
    while stack:
        v,l=stack.pop()
        used[v]=True
        dp[l:]=[INF]*(N-l)
        dp[bisect_right(dp,a[v]-1,hi=l)]=a[v]
        ans[v]=bisect_left(dp,INF,hi=l+1)-1
        for nv in edge[v]:
            if not used[nv]:
                stack.append((nv,l+1))
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left, bisect_right
from copy import deepcopy
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
    Length[0] = 1
    q = [(0, [A[0]])] # (vertex, dp)

    while q:
        v, dp = q.pop()
        for u in repn[v]:
            if Length[u] != 0:
                continue
            if A[u] > dp[-1]:
                Length[u] = Length[v] + 1
                new_dp = dp + [A[u]]
            else:
                Length[u] = Length[v]
                idx = bisect_right(dp, A[u])
                new_dp = deepcopy(dp)
                new_dp[idx] = A[u]
            q.append((u, new_dp))
    
    for ans in Length:
        print(ans)



    


    


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(n - 1)]

from collections import defaultdict
g = defaultdict(list)
for i in range(n - 1):
    u = uv[i][0] - 1
    v = uv[i][1] - 1
    g[u].append(v)
    g[v].append(u)

from bisect import bisect_left
ans = [0] * n
visited = [0] * n

def dfs(cur, dp):
    visited[cur] = 1
    idx = bisect_left(dp, a[cur])
    #print(cur, dp, idx)

    dp_new = dp.copy()
    if idx == len(dp_new):
        dp_new.append(a[cur])
    else:
        dp_new[idx] = a[cur]

    ans[cur] = len(dp_new)

    for target in g[cur]:
        if visited[target] == 0:
            dfs(target, dp_new)

dfs(0, [])

for _ans in ans:
    print(_ans)

Submission status: Runtime Error

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


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

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


DP = [10**9+7] * n
DP[0] = 0
ans = [0] * n


def dfs(node):
    node = node
    num = A[node]
    update_idx = bisect.bisect_left(DP, num)
    prev = DP[update_idx]
    DP[update_idx] = num
    lis = bisect.bisect_left(DP, 10**9+1) - 1
    ans[node] = lis
    for to in edges[node]:
        if not ans[to]:
            dfs(to)

    DP[update_idx] = prev


dfs(0)
for res in ans:
    print(res)

Submission status: Runtime Error

Solution code:

import bisect

def LIS(lis):

    seq = []

    for c in lis:
        ind = bisect.bisect_left(seq,c)

        if ind == len(seq):
            seq.append(c)
        else:
            seq[ind] = c

    return len(seq)


N = int(input())

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

lis = [ [] for i in range(N) ]

for i in range(N-1):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    lis[u].append(v)
    lis[v].append(u)

ans = [None] * N

def dfs(v,p,ln):

    ind = bisect.bisect_left(ln,a[v])

    if ind == len(ln):
        mt = None
        ln.append(a[v])
    else:
        mt = ln[ind]
        ln[ind] = a[v]

    ans[v] = len(ln)

    for nex in lis[v]:

        if nex != p:
            dfs(nex,v,ln)

    if mt == None:
        del ln[-1]
    else:
        ln[ind] = mt

    return

dfs(0,0,[])

for i in range(N):
    print (ans[i])

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())

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

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


def dfs(s):
    for d in T[s]:
        if not F[d]:
            F[d] = F[s][:]
            t = bisect.bisect_left(F[d], A[d])
            if t == len(F[d]):
                F[d].append(A[d])
            else:
                F[d][t] = A[d]
            dfs(d)


F[0] = [A[0]]
dfs(0)

for f in F:
    print(len(f))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

if n % 2 == 0:
    S = set()
    for i in range(m):
        a = i
        b = n - i - 1
        while b - a in S or a - b + n in S or b - a == a - b + n:
            b -= 1
        S.add(b - a)
        S.add(a - b + n)
        print(a + 1, b + 1)
else:
    for i in range(m):
        print(i + 1, m * 2 - i)

Submission status: Runtime Error

Solution code:
import bisect

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())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)

visited = [False]*N
visited[0] = True
answer = [1]*N

def dfs(v, dp):
    for nv in Edge[v]:
        if visited[nv]:
            continue
        
        visited[nv] = True
        if len(dp)==0 or A[nv]>dp[-1]:
            dp.append(A[nv])
            answer[nv] = len(dp)
            dfs(nv, dp)
            dp.pop()
        else:
            idx = bisect.bisect_left(dp, A[nv])
            temp = dp[idx]
            dp[idx] = A[nv]
            answer[nv] = len(dp)
            dfs(nv, dp)
            dp[idx] = temp
        
    return 

dfs(0, [A[0]])
answer[0] = 1
for a in answer:
    print(a)

Submission status: Runtime Error

Solution code:
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict

# import numpy as np

sys.setrecursionlimit(10**5 + 1)
input = sys.stdin.readline
write = sys.stdout.write


def read_item(cls=int):
    return cls(input())


def read_n_item(cls=int) -> list:
    return [cls(s) for s in input().split()]


def list2d(row, col, init_val=0) -> List[list]:
    return [[init_val] * col for _ in range(row)]


MOD = 10**9 + 7
# MOD = 998244353


N = read_item()
vals = read_n_item()
graph = defaultdict(list)

for _ in range(N-1):
    u, v = read_n_item()
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)


ans = [0] * N
ans[0] = 1
dp = [float('inf')] * N
dp[0] = vals[0]


def dfs(v, pre):
    for child in graph[v]:
        if child == pre:
            continue
        i = bisect_left(dp, vals[child])
        ans[child] = i+1

        temp = dp[i]
        dp[i] = vals[child]
        dfs(child, v)
        dp[i] = temp

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

Submission status: Runtime Error

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


def inp():
    return int(input())


def inpl():
    return list(map(int, input().split()))


def main():
    N = inp()
    aa = inpl()

    assert N != 2 * 10**5

    lines = [[] for _ in range(N)]
    for _ in range(N - 1):
        s, t = inpl()
        s -= 1
        t -= 1
        lines[s].append(t)
        lines[t].append(s)

    lines[0].append(-1)

    ansl = [0] * N

    stack = [(0, -1, [])]

    while stack:
        s, b, lis = stack.pop()
        a = aa[s]
        idx = bisect.bisect_left(lis, a)

        if len(lis) == idx:
            lis.append(a)
        else:
            lis[idx] = a

        ansl[s] = len(lis)

        if len(lines[s]) >= 3:
            for t in lines[s]:
                if t != b:
                    stack.append((t, s, lis.copy()))
        else:
            for t in lines[s]:
                if t != b:
                    stack.append((t, s, lis))

    print("\n".join(map(str, ansl)))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

N = int(input())
a = [0] + list(map(int, input().split()))
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)
lis = [float('inf')] * (N+1)
ans = [0] * (N+1)

def dfs(v, p):
    i = bisect_left(lis, a[v])
    ans[v] = i + 1
    tmp = lis[i]
    lis[i] = a[v]
    for c in G[v]:
        if c == p:
            continue
        dfs(c, v)
    lis[i] = tmp

dfs(1, 0)
print('\n'.join(map(str, ans[1:])))

Submission status: Runtime Error

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())

a = lmi()

adj = collections.defaultdict(set)
uv = llmi(N - 1)
for _u, _v in uv:
    u, v = _u - 1, _v - 1
    adj[u].add(v)
    adj[v].add(u)

trees = {}


class Tree:
    def __init__(self, index, parent_index=None):
        self.val = a[index]
        self.index = index
        self.parent = parent_index
        self.adj = []
        for v in adj[index]:
            if v == parent_index:
                continue
            self.adj.append(Tree(v, parent_index=self.index))
        self.ans = None
        trees[index] = self

    def __repr__(self):
        return '{}: {}'.format(self.index, [t.val for t in self.adj])

    def dp(self, current=None):
        if current is None:
            current = []
        v = bisect.bisect_left(current, self.val)
        # print(current)
        if v >= len(current):
            current.append(self.val)
        else:
            current[v] = self.val
        self.ans = len(current)
        for child_tree in self.adj:
            if child_tree is not self.adj[-1]:
                child_tree.dp(list(current))
            else:
                child_tree.dp(current)



root = Tree(0)
root.dp()
for i in range(N):
    print(trees[i].ans)

Submission status: Runtime Error

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


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())
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

    
def dfs(vs, lis, lis_len):
    
    lis = copy.copy(lis)
    if lis[-1] < a[vs]:
        lis.append(a[vs])
    else:
        index = bisect_left(lis, a[vs])
        lis[index] = a[vs]
    
    lis_len[vs] = len(lis)-1
    
    for ve in edge[vs]:
        if lis_len[ve] == -1:
            lis_len = dfs(ve, lis, lis_len)
    return lis_len


ans = dfs(0,[0],[-1]*n)
print("\n".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
import bisect
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):
    from_, to = map(int, input().split())
    edges[from_-1].append(to-1)
    edges[to-1].append(from_-1)


DP = [10**9+7] * n
DP[0] = 0
ans = [0] * n


def dfs(node):
    node = node
    num = A[node]
    lis = bisect.bisect_left(DP, num)

    prev = DP[lis]
    ans[node] = lis
    DP[lis] = num
    for to in edges[node]:
        if not ans[to]:
            dfs(to)

    DP[lis] = prev


dfs(0)
for res in ans:
    print(res)

Submission status: Runtime Error

Solution code:
import bisect

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())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)

visited = [False]*N
visited[0] = True
answer = [1]*N

def dfs(v, dp):
    for nv in Edge[v]:
        if visited[nv]:
            continue
        
        visited[nv] = True
        if A[nv]>dp[-1]:
            dp.append(A[nv])
            answer[nv] = len(dp)
            dfs(nv, dp)
            dp.pop()
        else:
            idx = bisect.bisect_left(dp, A[nv])
            temp = dp[idx]
            dp[idx] = A[nv]
            answer[nv] = len(dp)
            dfs(nv, dp)
            dp[idx] = temp
        
    return 

dfs(0, [A[0]])
answer[0] = 1
for a in answer:
    print(a)

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
from sys import setrecursionlimit

setrecursionlimit(10**8)
n = int(input())
A = list(map(int, input().split()))
gr = []
for i in range(n):
    gr.append([])
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    gr[a].append(b)
    gr[b].append(a)
ans = [0] * n
dp = [10 ** 10 for i in range(n)]
dp[0] = -10 ** 10
kek = 1
used = {0}


def dfs(v):
    global kek
    j = bisect_right(dp, A[v] - 1)
    old = -1
    if dp[j - 1] < A[v] < dp[j]:
        old = dp[j]
        dp[j] = A[v]
        if kek == j:
            for h in range(kek + 1, n):
                if dp[h] == 10 ** 10:
                    kek = h
                    break
            if kek == j:
                kek = n
    ans[v] = kek - 1
    for u in gr[v]:
        if u not in used:
            used.add(u)
            dfs(u)
    dp[j] = old
    if kek > j and old == 10 ** 10:
        kek = j


dfs(0)
print(*ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect


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


res = [None]*N
dp = [float('inf') for _ in range(N)]

def rec(v, ml):
    """
    dp[l]: min tail value of increasing subsequence of length l+1
    """
    a = A[v]
    i = bisect(dp, a)
    ml += int(ml == i)
    res[v] = ml

    orig = dp[i]
    dp[i] = a
    for u in adj[v]:
        if res[u] is None:
            rec(u, ml)
    dp[i] = orig

rec(0, 0)

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
from sys import setrecursionlimit

setrecursionlimit(10**8)
n = int(input())
A = list(map(int, input().split()))
gr = []
for i in range(n):
    gr.append([])
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    gr[a].append(b)
    gr[b].append(a)
ans = [0] * n
dp = [10 ** 10 for i in range(n)]
dp[0] = -10 ** 10
kek = 1
used = {0}


def dfs(v):
    global kek
    j = bisect_right(dp, A[v])
    old = -1
    if dp[j - 1] < A[v] < dp[j]:
        old = dp[j]
        dp[j] = A[v]
        if kek == j:
            for h in range(kek + 1, n + 1):
                if dp[h] == 10 ** 10:
                    kek = h
                    break
    ans[v] = kek - 1
    for u in gr[v]:
        if u not in used:
            used.add(u)
            dfs(u)
    dp[j] = old
    if kek > j and old == 10 ** 10:
        kek = j


dfs(0)
print(*ans)

Submission status: Runtime Error

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())

a = lmi()

adj = collections.defaultdict(set)
uv = llmi(N - 1)
for _u, _v in uv:
    u, v = _u - 1, _v - 1
    adj[u].add(v)
    adj[v].add(u)

trees = {}


class Tree:
    def __init__(self, index, parent_index=None):
        self.val = a[index]
        self.index = index
        self.parent = parent_index
        self.adj = []
        for v in adj[index]:
            if v == parent_index:
                continue
            self.adj.append(Tree(v, parent_index=self.index))
        self.ans = None
        trees[index] = self

    def __repr__(self):
        return '{}: {}'.format(self.index, [t.val for t in self.adj])

    def dp(self, current=None):
        if current is None:
            current = []
        v = bisect.bisect_left(current, self.val)
        # print(current)
        if v >= len(current):
            current.append(self.val)
        else:
            current[v] = self.val
        # print('--', current)
        self.ans = len(current)
        for child_tree in self.adj:
            child_tree.dp(list(current))


root = Tree(0)
root.dp()
for i in range(N):
    print(trees[i].ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

dq = deque([1])
euler = [1]
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)


lis = [0] * (N+1)
lis[1] = 1

def f(v,l):
    if visited[v]:
        return
    visited[v] = True
    i = bisect.bisect_right(l,a[v-1])
    l[i] = a[v-1]
    lis[v] = l.index(inf) - 1
    for nv in g[v]:
        if not visited[nv]:
            f(nv,l[:])

l = [inf] * (N+1)
l[0] = a[0]
f(1,l)

for i in range(1,N+1):
    print(lis[i])

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left, bisect_right
from copy import deepcopy
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
    Length[0] = 1
    q = [(0, [A[0]])] # (vertex, dp)

    while q:
        v, dp = q.pop()
        for u in repn[v]:
            if Length[u] != 0:
                continue
            if A[u] > dp[-1]:
                Length[u] = Length[v] + 1
                new_dp = dp + [A[u]]
            else:
                Length[u] = Length[v]
                idx = bisect_right(dp, A[u])
                new_dp = deepcopy(dp)
                new_dp[idx] = A[u]
            q.append((u, new_dp))
    
    for ans in Length:
        print(ans)



    


    


if __name__ == "__main__":
    main()