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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May  2 22:08:16 2020

@author: reira
"""
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

N = int(input())
A = np.array(list(map(int,input().split())))
path = [[False] * N for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True

csr = csr_matrix(path)
step, p = dijkstra(csr, unweighted=True, return_predecessors=True)

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

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]

def LIS(seq):
    import bisect
    L = [seq[0]]
    for i in range(len(seq)):
        if seq[i] > L[-1]:
            L.append(seq[i])
        else:
            L[bisect.bisect_left(L, seq[i])] = seq[i]
    return(len(L))


for k in range(N):
    print(LIS(list(A[get_path(0, k, p)])))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
a = [0] + list(map(int, input().split()))
g = [[] for i in range(n+1)]
for i in range(n-1):
    x, y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)


q = [(1, [a[1]])]
ans = [None]*(n+1)
ans[1] = 1
while q:
    now, now_l = q.pop()
    count = 0
    for next in g[now]:
        if ans[next] == None:
            count += 1
    if count >= 2:
        for next in g[now]:
            if ans[next] == None:
                if a[next] > now_l[-1]:
                    q.append((next, now_l + [a[next]]))
                    ans[next] = len(now_l) + 1
                else:
                    next_l = now_l[:]
                    next_l[bisect.bisect_left(now_l, a[next])] = a[next]
                    q.append((next, next_l))
                    ans[next] = len(now_l)

    else:
        for next in g[now]:
            if ans[next] == None:
                if a[next] > now_l[-1]:
                    now_l.append(a[next])
                    q.append((next, now_l))
                    ans[next] = len(now_l)
                else:
                    now_l[bisect.bisect_left(now_l, a[next])] = a[next]
                    q.append((next, now_l))
                    ans[next] = len(now_l)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

sys.setrecursionlimit(10 ** 7)


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: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import deque
import copy
def lis(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a > L[-1]:
            # Lの末尾よりaが大きければ増加部分列を延長できる
            L.append(a)
        else:
            # そうでなければ、「aより小さい最大要素の次」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_left(L, a)] = a
    return len(L)
n = int(input())
a = tuple(map(int, input().split()))
G = [[] for _ in range(n+1)]
for i in range(n-1):
    u,v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)

letu = [[] for _ in range(n+1)]
letu[1].append(1)
que = deque([1])

while que:
    q = que.popleft()

    for nq in G[q]:
        let = copy.deepcopy(letu[q])
        if letu[nq] != []: #seen配列としても使う。seenないと閉路でWA
            continue
        let = let + [nq]
        letu[nq] = let
        que.append(nq)
for j in range(1,n+1):
    tmp = [a[aa-1] for aa in letu[j]]
    print(lis(tmp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N=int(input())
alist=[0]+list(map(int,input().split()))

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

def LIS(path,seq):
  import bisect  
  LIS = [seq[0]]
  for i in range(len(seq)):
    if seq[i] > LIS[-1]:
      LIS.append(seq[i])
    else:
      LIS[bisect.bisect_left(LIS, seq[i])]=seq[i]
    #print(i,seq[i],len(LIS))
    answer_dic[path[i]]=len(LIS)
   
  return LIS
      
def dfs(u,path,ls):    
  visited[u]=True
  #print(u,ls)
  #answer_dic[u]=ls

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      dfs(v,path+[v],ls+[alist[v]])
      cnt+=1
      
  if cnt==0:
    #compute LIS of ls
    #print(u,ls)
    LIS(path,ls)
    #print(LIS(ls))

visited=[False]*(N+1)
answer_dic={}

dp=[]
dfs(1,[1],[alist[1]])
#print(answer_dic)

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

Submission status: Time Limit Exceeded

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


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: Time Limit Exceeded

Solution code:
import bisect
import collections
from collections import deque

n=int(input())
a= list(map(int, input().split()))
a1= [list(map(int, input().split())) for i in range(n-1)]

g=[[] for i in range(n)]

for x,y in a1:
    g[x-1].append(y-1)
    g[y-1].append(x-1)


vis = [0] * n
order = []
parent = [0] * (n + 1)
s = [0]

while len(s):
    x = s.pop()
    vis[x] = 1
    order.append(x)
    for y in g[x]:
        if vis[y]: continue
        s.append(y)
        parent[y] = x


ans=[0]*n
LIS = [[0] for i in range(n)]

for x in order:
    LIS[x]=LIS[parent[x]][:]
    if a[x] > LIS[x][-1]:
        LIS[x].append(a[x])
    else:
        LIS[x][bisect.bisect_left(LIS[x], a[x])] = a[x]
    ans[x]=len(LIS[x])-1

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

Submission status: Time Limit Exceeded

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])
visited = [False]*(N+1)

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

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

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

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

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

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    a = list(map(int,input().split()))
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        p,q = map(int,input().split())
        p -= 1
        q -= 1
        g[p].append(q)
        g[q].append(p)
    dis = [10**10]*n
    dis[0] = 0
    que = deque()
    que.append(0)
    pr = [0 for _ in range(n)]
    pr[0] = 1
    ans = ['' for _ in range(n)]
    ans[0] = [a[0]]
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] <= dis[go] + 1:
                continue
            lis = copy.copy(ans[go])
            if a[g[go][i]] > lis[-1]:
                lis.append(a[g[go][i]])
            else:
                lis[bisect.bisect_left(lis,a[g[go][i]])] = a[g[go][i]]
            ans[g[go][i]] = lis
            dis[g[go][i]] = dis[go] + 1
            que.append(g[go][i])
    for i in range(n):
        print(len(ans[i]))
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
n = int(input())
a = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

d = [0 for _ in range(n)]
memo = [[] for _ in range(n)]
seen = [False for _ in range(n)]
que = deque()
que.append(0)
memo[0] = [a[0]]
d[0] = 1
seen[0] = True

while len(que):
    cur = que.popleft()
    for to in edges[cur]:
        if not seen[to]:
            seen[to] = True
            memo[to] = memo[cur].copy()
            if memo[cur][-1] < a[to]:
                d[to] = d[cur] + 1
                memo[to].append(a[to])
            else:
                d[to] = d[cur]
                memo[to][bisect.bisect_left(memo[to], a[to])] = a[to]
            que.append(to)
    memo[cur] = []

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
from copy import copy
from bisect import bisect_left
import sys

input = sys.stdin.buffer.readline

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

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

INF = 10**10
lis = [INF] * n
d = deque([(0, -1, lis)])
ans = [-1] * n

while d:
    cur, pre, l = d.pop()

    l2 = copy(l)
    l2[bisect_left(l2, a[cur])] = a[cur]
    ans[cur] = bisect_left(l2, INF)

    for i in neighbor[cur]:
        if i != pre:
            d.append((i, cur, l2))

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

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

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [[float("inf") for _ in range(n+1)] for i in range(n)]
dp[0][0] = -1
used = [0 for i in range(n)]
used[0] = 1

def dfs(pos, dp):
    idx = bisect(dp[pos], al[pos] - 1)
    dp[pos][idx] = min(al[pos], dp[pos][idx])
    ansl[pos] = max(i for i in range(n+1) if dp[pos][i] < float("inf"))
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dp[v] = dp[pos][:]
            dfs(v, dp)


dfs(0, dp)
flag = False
for i in range(n):
    print(ansl[i])

Submission status: Time Limit Exceeded

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()

    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: Time Limit Exceeded

Solution code:
n=int(input())
l=[0]+list(map(int,input().split()))
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
s=1
ans=[0 for i in range(n+1)]

from bisect import bisect_left, bisect_right
INF=float('inf')

import sys
sys.setrecursionlimit(10**6)
dep=[-1 for i in range(n+1)]
def dfs(s,d,c):
    dep[s]=d
    cc=c[:]
    cc[bisect_left(cc,l[s])]=l[s]
    ans[s]=bisect_left(cc,INF)
    for i in edge[s]:
        if dep[i]==-1:
            dfs(i,d+1,cc)
c=[INF]*len(l)
dfs(1,0,c)
for i in range(1,n+1):
    print(ans[i])

Submission status: Time Limit Exceeded

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

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

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

INF = 10**10
lis = [INF] * n
d = deque([(0, -1, lis)])
ans = [-1] * n

while d:
    cur, pre, l = d.pop()

    l2 = copy(l)
    l2[bisect_left(l2, a[cur])] = a[cur]
    ans[cur] = bisect_left(l2, INF)

    for i in neighbor[cur]:
        if i != pre:
            d.append((i, cur, l2))

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import deque
import copy
def lis(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a > L[-1]:
            # Lの末尾よりaが大きければ増加部分列を延長できる
            L.append(a)
        else:
            # そうでなければ、「aより小さい最大要素の次」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_left(L, a)] = a
    return len(L)
n = int(input())
a = tuple(map(int, input().split()))
G = [[] for _ in range(n+1)]
for i in range(n-1):
    u,v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)

letu = [[] for _ in range(n+1)]
letu[1].append(1)
que = deque([1])

while que:
    q = que.popleft()

    for nq in G[q]:
        let = copy.deepcopy(letu[q])
        if letu[nq] != []: #seen配列としても使う。seenないと閉路でWA
            continue
        let = let + [nq]
        letu[nq] = let
        que.append(nq)
for j in range(1,n+1):
    tmp = []
    for aa in letu[j]:
        tmp.append(a[aa-1])
    print(lis(tmp))

Submission status: Time Limit Exceeded

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

read = sys.stdin.read
readline = sys.stdin.readline


def main():
    N = int(readline())
    a = tuple(map(int, readline().split()))
    uv = map(int, read().split())
    graph = [[] for _ in range(N)]
    for u, v in zip(uv, uv):
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)

    answer = [-1] * N
    stack = deque([(0, [a[0]])])
    answer[0] = 1

    while stack:
        V, LIS = stack.pop()
        if V == 0:
            for v in graph[V]:
                if answer[v] != -1:
                    continue
                tmp=a[v]
                if tmp > LIS[-1]:
                    new_LIS = LIS[:] + [tmp]
                else:
                    new_LIS = LIS[:]
                    new_LIS[bisect_left(new_LIS, tmp)] = tmp
                answer[v] = len(new_LIS)
                stack.append((v, new_LIS))
            continue
        if len(graph[V]) > 2:
            for v in graph[V]:
                tmp=a[v]
                if answer[v] != -1:
                    continue
                if tmp > LIS[-1]:
                    new_LIS = LIS[:] + [tmp]

                else:
                    new_LIS = LIS[:]
                    new_LIS[bisect_left(new_LIS, tmp)] = tmp
                answer[v] = len(new_LIS)
                stack.append((v, new_LIS))
        else:
            for v in graph[V]:
                tmp=a[v]
                if answer[v] != -1:
                    continue
                if tmp > LIS[-1]:
                    LIS += [tmp]
                else:
                    LIS[bisect_left(LIS, tmp)] = tmp
                answer[v] = len(LIS)
                stack.append((v, LIS))

    print('\n'.join(map(str, answer)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:



from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
    
ns = defaultdict(set)
for _ in range(n-1):
    u,v = [int(c) for c in input().split()]
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

from bisect import bisect_left
 
l = [a[0]]
# for a in A[1:]:
#     if a > L[-1]:
#         # Lの末尾よりaが大きければ増加部分列を延長できる
#         L.append(a)
#     else:
#         # そうでなければ、「aより小さい最大要素の次」をaにする
#         # 該当位置は、二分探索で特定できる
#         L[bisect_left(L, a)] = a
# return len(L)

q = [(0, -1, l)]
ans = [None] * n
while q:
    u, prev, lst = q.pop()
    ans[u] = len(lst)
    for v in ns[u]:
        if prev==v:
            continue
        aa = a[v]
        if aa > lst[-1]:
            tmp = lst + [aa]
        else:
            tmp = list(lst)
            tmp[bisect_left(lst, aa)] = aa
#         print(tmp)
        q.append((v, u, tmp))
print("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
# import heapq
# import math
# import random
import sys
# from collections import Counter, defaultdict, deque
# from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
# from functools import lru_cache, reduce
# from itertools import combinations, combinations_with_replacement, product, permutations
# from operator import add, mul, sub

sys.setrecursionlimit(100000)
# input = sys.stdin.buffer.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


ans = [-1] * (2*10**5+1)

@mt
def slv(N, A, UV):
    A.insert(0, -1)
    g = [list() for _ in range(0, N+1)]
    for u, v in UV:
        g[u].append(v)
        g[v].append(u)


    def dfs(u, p, dp):
        global ans

        for v in g[u]:
            if v == p:
                continue

            i = bisect.bisect_left(dp, A[v])
            if len(dp) <= i:
                dp.append(A[v])
                ans[v] = len(dp)
                dfs(v, u, dp)
                dp.pop()
            else:
                b = dp[i]
                dp[i] = A[v]
                ans[v] = len(dp)
                dfs(v, u, dp)
                dp[i] = b
    dp = [A[1]]
    dfs(1, 0, dp)

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

    # return ans[:N]


def main():
    N = read_int()
    A = read_int_n()
    UV = [read_int_n() for _ in range(N-1)]
    (slv(N, A, UV))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    dp = [[False] for i in range(n)]
    dp[0] = [l[0]]
    
    q = deque([])
    q.append(0)
    while q:
        now = q.popleft()

        for nex in e[now]:
            if dp[nex] == [False]:
                dp[nex] = deepcopy(dp[now])
                if l[nex] > dp[nex][-1]:
                        dp[nex].append(l[nex])
                else:
                    dp[nex][bisect.bisect_left(dp[nex], l[nex])] = l[nex]
                q.append(nex)
    
    for i in dp:
        print(len(i))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

n = int(input())
a = list(map(int, input().split()))
to=[list() 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)

d= deque()
INF=10010001001
dpinit = [INF]*n
dpinit[0]=a[0]
d.append((0,-1,copy(dpinit)))
ansls=[0]*n
ansls[0]=1
while d:
    u,p,dp = d.popleft()
    for v in to[u]:
        if v==p:
            continue
        dp2=copy(dp)
        idx=bisect.bisect_left(dp2,a[v])
        dp2[idx]=a[v]
        ansls[v]=bisect.bisect_left(dp2,INF)
        d.append((v,u,copy(dp2)))

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


def main():
    N = int(input())
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [], True)]
    while len(q):
        cur, prev, lis, override = q.pop()
        idx = bisect_left(lis, A[cur])
        if override:
            nxt_lis = lis
        else:
            nxt_lis = list(lis)
        if idx == len(nxt_lis):
            nxt_lis.append(A[cur])
        else:
            nxt_lis[idx] = A[cur]
        ans[cur] = len(nxt_lis)
        nxt_override = (cur != 0)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, nxt_lis, nxt_override))
            nxt_override = False
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
import bisect

def get_lis(seq):

    LIS = [seq[0]]
    for i in range(len(seq)):
        if seq[i] > LIS[-1]:
            LIS.append(seq[i])
        else:
            LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
    return len(LIS)

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

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]

n = int(input())
a = list(map(int, input().split()))
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    graph[u-1][v-1] = 1
    graph[v-1][u-1] = 1
graph = np.array(graph)

d, p = shortest_path(graph, return_predecessors=True)

for i in range(n):
    seq = []
    t = get_path(0, i, p)
    for index in t:
        seq.append(a[index])
    print(get_lis(seq))

Submission status: Time Limit Exceeded

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


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


def main():
    N = int(input())
    A = inpl()
    edges = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v = inpl()
        edges[u].append(v)
        edges[v].append(u)
    DPs = [None] * (N + 1)
    DPs[0] = []

    Q = deque()
    Q.append(1)
    parent = [-1] * (N + 1)
    parent[1] = 0
    while Q:
        nv = Q.popleft()
        DPs[nv] = DPs[parent[nv]].copy()
        t = bisect(DPs[nv], A[nv - 1])
        if t >= len(DPs[nv]):
            DPs[nv].append(A[nv - 1])
        else:
            DPs[nv][t] = A[nv - 1]

        for kouho in edges[nv]:
            if parent[kouho] == -1:
                Q.append(kouho)
                parent[kouho] = nv

    for i in range(1, N + 1):
        print(len(DPs[i]))
    # print(edges)
    # print(parent)
    # print(DPs)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
a = [0] + list(map(int, input().split()))
g = [[] for i in range(n+1)]
for i in range(n-1):
    x, y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)


q = [(1, [a[1]])]
ans = [None]*(n+1)
ans[1] = 1
while q:
    now, now_l = q.pop()
    for next in g[now]:
        if ans[next] == None:
            if a[next] > now_l[-1]:
                q.append((next, now_l + [a[next]]))
                ans[next] = len(now_l) + 1
            else:
                next_l = now_l[:]
                next_l[bisect.bisect_left(now_l, a[next])] = a[next]
                q.append((next, next_l))
                ans[next] = len(now_l)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline


def main():
    N = int(readline())
    a = tuple(map(int, readline().split()))
    uv = map(int, read().split())
    graph = [[] for _ in range(N)]
    for u, v in zip(uv, uv):
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)

    answer = [-1] * N
    stack = [(0, [a[0]])]
    answer[0] = 1

    while stack:
        V, LIS = stack.pop()
        if V == 0:
            for v in graph[V]:
                if answer[v] != -1:
                    continue
                tmp=a[v]
                if tmp > LIS[-1]:
                    new_LIS = LIS[:] + [tmp]

                else:
                    new_LIS = LIS[:]
                    new_LIS[bisect_left(new_LIS, tmp)] = tmp
                answer[v] = len(new_LIS)
                stack.append((v, new_LIS))
            continue
        if len(graph[V]) > 2:
            for v in graph[V]:
                tmp=a[v]
                if answer[v] != -1:
                    continue
                if tmp > LIS[-1]:
                    new_LIS = LIS[:] + [tmp]

                else:
                    new_LIS = LIS[:]
                    new_LIS[bisect_left(new_LIS, tmp)] = tmp
                answer[v] = len(new_LIS)
                stack.append((v, new_LIS))
        else:
            for v in graph[V]:
                tmp=a[v]
                if answer[v] != -1:
                    continue
                if tmp > LIS[-1]:
                    LIS += [tmp]
                else:
                    LIS[bisect_left(LIS, tmp)] = tmp
                answer[v] = len(LIS)
                stack.append((v, LIS))

    print('\n'.join(map(str, answer)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def dijkstra(n,EdgeMatrix,start,a):

    NodeList=queue.PriorityQueue() #探索対象の頂点
    Distance=[float('inf')]*n #頂点0からの最短経路
    used=[False]*n #頂点の使用情報
    point=[[] for i in range(n)]

    Distance[start]=0 #0から0までの距離は0
    used[start]=True #0から探索を始める
    LastNode=start #最新の頂点
    Flag=True #探索対象が残っている時はTrue

    while Flag:
        Flag=False
        for i in range(len(EdgeMatrix[LastNode])):
            #探索していない頂点へ距離の短い辺があればキューに追加
            Edge=EdgeMatrix[LastNode][i]
            if used[Edge[0]]==False and Distance[Edge[0]]>Distance[LastNode]+Edge[1]:
                    Distance[Edge[0]]=Distance[LastNode]+Edge[1]
                    NodeList.put([Distance[Edge[0]],Edge[0],LastNode])

        #最も近い探索していない頂点
        while not NodeList.empty():
            minNode=NodeList.get()
            if used[minNode[1]]==False:
                last=minNode[2]
                Flag=True
                break
        
        s=[]
        s.extend(point[last])
        s.extend([a[last]])
        point[minNode[1]]=s
        LastNode=minNode[1] #最新の頂点を更新
        used[minNode[1]]=True #頂点の使用情報を更新
    return Distance,point
    
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

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

#頂点0からの最短経路
Distance,point=dijkstra(n,EdgeMatrix,0,a)
print(1)
for i in range(1,n):
    point[i].extend([a[i]])
    res=LIS(point[i],len(point[i]))
    print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
n = int(input())
a = list(map(int, input().split()))
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

d = [0 for _ in range(n)]
memo = [[] for _ in range(n)]
seen = [False for _ in range(n)]
que = deque()
que.append(0)
memo[0] = [a[0]]
d[0] = 1
seen[0] = True

while len(que):
    cur = que.popleft()
    for to in edges[cur]:
        if not seen[to]:
            seen[to] = True
            memo[to] = memo[cur].copy()
            if memo[cur][-1] < a[to]:
                d[to] = d[cur] + 1
                memo[to].append(a[to])
            else:
                d[to] = d[cur]
                memo[to][bisect.bisect_left(memo[to], a[to])] = a[to]
            que.append(to)

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