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:
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])
dist = [-1]*(n+1)
dist[1] = 0
while que:
    q = que.popleft()
    d = dist[q]
    for nq in G[q]:

        if dist[nq] != -1: #seen配列としても使う。seenないと閉路でWA
            continue
        dist[nq] = d + 1

        letu[nq] = letu[q]+ [nq]
        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:
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

from collections import deque
q = deque([(0, [])])
visited[0] = 1

while q:
    cur, dp = q.popleft()

    idx = bisect_left(dp, a[cur])
    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:
            visited[target] = 1
            q.append((target, dp_new))


for _ans in ans:
    print(_ans)

Submission status: Time Limit Exceeded

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

n = int(input())

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

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

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

q = deque()


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

seen = [0 for i in range(n)]
q.append([0, [0], [0]])
seen[0] = 1

while len(q):
    cur = q.popleft()

    node_num = cur[0]
    prev_stream = copy.deepcopy(cur[1])
    prev_lis = copy.deepcopy(cur[2])

    cur_a = a_l[node_num]

    prev_stream.append(cur_a)
    cur_stream = prev_stream

    if cur_a > prev_lis[-1]:
        prev_lis.append(cur_a)
        cur_lis = prev_lis
    else:
        prev_lis[bisect_left(prev_lis, cur_a)] = cur_a
        cur_lis = prev_lis

    ans[node_num] = len(cur_lis) - 1

    for next in tree[node_num]:
        if seen[next] == 0:
            q.append([next, cur_stream, cur_lis])
            seen[next] = 1

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

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)


    ans = [[] for i in range(n)]
    ans[0] = [[l[0]],1]
    q = deque([])
    q.append((0,-1))
    while q:
        now,bef = q.popleft()

        for nex in e[now]:
            if nex != bef:
                a = l[nex]
                b = ans[now][1]
                
                c = deepcopy(ans[now][0])
                if a > c[-1]:
                        c.append(l[nex])
                        ans[nex] = [c,b+1]
                else:
                    c[bisect.bisect_left(c, l[nex])] = l[nex]
                    ans[nex] = [c,b]
                q.append((nex,now))

    
    for i in ans:
        print(i[1])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000000)
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, diffs):
        v = bisect.bisect_left(current, self.val)
        if v >= len(current):
            diffs.append((v, None))
            current.append(self.val)
        else:
            diffs.append((v, current[v]))
            current[v] = self.val
        self.ans = len(current)
        for child_tree in self.adj:
            child_tree.dp(current, diffs)
            index, val = diffs.pop()
            if val is None:
                current.pop()
            else:
                current[index] = val


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
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 path[i] in answer_dic:
      LIS=seq_dic[path[i]]
    elif 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)
    seq_dic[path[i]]=list(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={}
seq_dic={}
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:
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 = list(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: 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])
dist = [-1]*(n+1)
dist[1] = 0
while que:
    q = que.popleft()
    d = dist[q]
    for nq in G[q]:
        let = copy.deepcopy(letu[q])
        if dist[nq] != -1: #seen配列としても使う。seenないと閉路でWA
            continue
        dist[nq] = d + 1

        letu[nq] = let+ [nq]
        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**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)
    if k < i:
        l.append(inf)
        k += 1
    l[i] = A 
    lis[v] = k
    #lis[v] = l.index(inf)
    for nv in g[v]:
        if not visited[nv]:
            f(nv,l[:],k)

l = [inf] * 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
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
from collections import deque


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


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

Solution code:
#import numpy as np
import heapq
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

edge = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    edge[x].append(y)
    edge[y].append(x)
#print(edge)

def fLIS(l: list):
    LIS = [l[0]]
    for i in range(len(l)):
        if l[i] > LIS[-1]:
            LIS.append(l[i])
        else:
            LIS[bisect_left(LIS, l[i])] = l[i]
    return len(LIS)

ress = [1]*N
seen = [0]*N

stack = deque()
stack.append([(0, [A[0]])])
while stack[0]:
    nstack = []
    cstack = stack.pop()
    #print('cstack:', cstack)
    for val in cstack:
        #print(' val', val)
        index, l = val
        seen[index] = 1
        ress[index] = fLIS(l)
        for edgei in edge[index]:
            if seen[edgei] == 0:
                #print(' edgei', edgei)
                #print(' A', A)
                nstack.append((edgei, l+[A[edgei]]))
    #print(' nstack', nstack)
    stack.append(nstack)

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

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys
sys.setrecursionlimit(1000000)

def calc(arr, query):
    ret = 0
    # print(arr)\
    for q in query:
        if arr[q[1] - 1] - arr[q[0] - 1] == q[2]:
            ret += q[3]

    return ret

def dfs(tree, nums, answers, current, LIS, visited):
    # if current >= 7:
        # print(current, LIS)
    visited[current] = 1
    nc = nums[current]
    if nc > LIS[-1]:
        LIS.append(nc)
    else:
        ins = bisect_left(LIS, nc)
        if LIS[ins] != nc:
            if ins == 0:
                LIS[ins] = nc
            elif LIS[ins-1] != nc:
                LIS[ins] = nc
    answers[current] = len(LIS)
    # 分岐するときはLIS複製
    # そうでなければポインタ私
    if len(tree[current]) == 1 and current != 0:
        return
    if len(tree[current]) == 2 and current != 0:
        for nx in tree[current]:
            if not visited[nx]:
                dfs(tree, nums, answers, nx, LIS, visited)
        return
    else:
        # org = LIS
        # print("bunki", current)
        char = 1
        for nx in tree[current]:
            if not visited[nx]:
                if char != len(tree[current]):
                    LIScp = copy.copy(LIS)
                else:
                    LIScp = LIS
                dfs(tree, nums, answers, nx, LIScp, visited)
            char += 1
        return



def main():
    n = getN()
    nums = getList()
    tree = [[] for _ in range(n)]
    for i in range(n - 1):
    # start, end, cost
        a, b = getList()
        # 0-indexed
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)

    # print(tree)
    answers = [0 for i in range(n)]
    answers[0] = 1
    LIS = [nums[0]]
    visited = [0 for i in range(n)]
    visited[0] = 1
    dfs(tree, nums, answers, 0, LIS, visited)

    for ans in answers:
        print(ans)

if __name__ == "__main__":
    main()

"""
5
1 2 3 4 5
1 2
2 3
3 4
4 5


"""

Submission status: Time Limit Exceeded

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

from bisect import bisect_left

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

adj = [[] for _ in range(n)]
for u, v in uv:
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

arrived = [False] * n

ans = [None] * n
ans[0] = 1


def dfs(u, dp, l):
    arrived[u] = True
    for v in adj[u]:
        if not arrived[v]:
            idx = bisect_left(dp, a[v])
            if idx == l:
                dp_nxt = dp + [a[v]]
                ans[v] = l + 1
                dfs(v, dp_nxt, l + 1)
            else:
                dp_nxt = dp[:idx] + [min(a[v], dp[idx])] + dp[idx+1:]
                ans[v] = l
                dfs(v, dp_nxt, l)


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline



def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    dp = [[A[0]] for _ in range(N)]
    B = [[A[0]] for _ in range(N)]
    dist = [-1]*N
    dist[0] = 0
    queue = deque()
    queue.append([0,-1])
    while queue:
        Q = queue.popleft()
        now, pre = Q
        d = dist[now]
        for i in edge[now]:
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            queue.append((i,now))
            B[i] = B[now] + [A[i]]
            dp[i] = dp[now].copy()
            if B[i][-1] > dp[i][-1]:
                dp[i].append(B[i][-1])
            else:
                dp[i][bisect.bisect_left(dp[i], B[i][-1])] = B[i][-1]

    for i in range(N):
        print(len(dp[i]))

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

MOD = 10 ** 9 + 7

def main():
    for _ in inputt(1):
        n,  = inputi()
        P = [[] for _ in range(n + 1)]
        R = [1] * (n + 1)
        A = [0] + inputl()
        for _ in range(n - 1):
            a, b = inputi()
            P[a].append(b)
            P[b].append(a)
        Z = [0] * (n + 1)
        def T(i, D):
            if not Z[i]:
                Z[i] = 1
                nD = D.copy()
                for d, v in D.items():
                    if A[i] > v:
                        nD[d + 1] = min(nD.get(d + 1, inf), A[i])
                R[i] = max(nD)
                for p in P[i]:
                    T(p, nD)
        T(1, {0: -inf})
        print(*R[1:], split="\n")


# region M


# region import

from math import *
from heapq import *
from itertools import *
from functools import reduce, lru_cache, partial
from collections import Counter, defaultdict
import re, copy, operator, cmath
import sys, io, os, builtins
sys.setrecursionlimit(200100)

# endregion

# region fastio

BUFSIZE = 8192
class FastIO(io.IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(io.IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
def print(*args, **kwargs):
    if args:
        sys.stdout.write(str(args[0]))
        split = kwargs.pop("split", " ")
        for arg in args[1:]:
            sys.stdout.write(split)
            sys.stdout.write(str(arg))
    sys.stdout.write(kwargs.pop("end", "\n"))
def debug(*args, **kwargs):
    print("debug", *args, **kwargs)
    sys.stdout.flush()
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip()
inputt = lambda t = 0: range(t) if t else range(int(input()))
inputs = lambda: input().split()
inputi = lambda k = int: map(k, inputs())
inputl = lambda t = 0, k = lambda: list(inputi()): [k() for _ in range(t)] if t else list(k())

# endregion

# region bisect

def len(a):
    if isinstance(a, range):
        return -((a.start - a.stop) // a.step)
    return builtins.len(a)
def bisect_left(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if key(a[mid]) < x: lo = mid + 1
        else: hi = mid
    return lo
def bisect_right(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if x < key(a[mid]): hi = mid
        else: lo = mid + 1
    return lo
def insort_left(a, x, key = None, lo = 0, hi = None):
    lo = bisect_left(a, x, key, lo, hi)
    a.insert(lo, x)
def insort_right(a, x, key = None, lo = 0, hi = None):
    lo = bisect_right(a, x, key, lo, hi)
    a.insert(lo, x)
do_nothing = lambda x: x
bisect = bisect_right
insort = insort_right
def index(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi and key(a[i]) == x: return a[i]
    if default != None: return default
    raise ValueError
def find_lt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_le(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_gt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError
def find_ge(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError

# endregion

# region csgraph
# TODO

class Tree:
    def __init__(n):
        self._n = n
        self._conn = [[] for _ in range(n)]
        self._list = [0] * n
    def connect(a, b):
        pass

# endregion

# region ntheory

class Sieve:
    def __init__(self):
        self._n = 6
        self._list = [2, 3, 5, 7, 11, 13]
    def extend(self, n):
        if n <= self._list[-1]: return
        maxbase = int(n ** 0.5) + 1
        self.extend(maxbase)
        begin = self._list[-1] + 1
        newsieve = [i for i in range(begin, n + 1)]
        for p in self.primerange(2, maxbase):
            for i in range(-begin % p, len(newsieve), p):
                newsieve[i] = 0
        self._list.extend([x for x in newsieve if x])
    def extend_to_no(self, i):
        while len(self._list) < i: 
            self.extend(int(self._list[-1] * 1.5))
    def primerange(self, a, b):
        a = max(2, a)
        if a >= b: return
        self.extend(b)
        i = self.search(a)[1]
        maxi = len(self._list) + 1
        while i < maxi:
            p = self._list[i - 1]
            if p < b:
                yield p
                i += 1
            else: return
    def search(self, n):
        if n < 2: raise ValueError
        if n > self._list[-1]: self.extend(n)
        b = bisect(self._list, n)
        if self._list[b - 1] == n: return b, b
        else: return b, b + 1
    def __contains__(self, n):
        if n < 2: raise ValueError
        if not n % 2: return n == 2
        a, b = self.search(n)
        return a == b
    def __getitem__(self, n):
        if isinstance(n, slice):
            self.extend_to_no(n.stop + 1)
            return self._list[n.start: n.stop: n.step]
        else:
            self.extend_to_no(n + 1)
            return self._list[n]

sieve = Sieve()
def isprime(n):
    if n <= sieve._list[-1]:
        return n in sieve
    for i in sieve:
        if not n % i: return False
        if n < i * i: return True
prime = sieve.__getitem__
primerange = lambda a, b = 0: sieve.primerange(a, b) if b else sieve.primerange(2, a)
def factorint(n):
    factors = []
    for i in sieve:
        if n < i * i: break
        while not n % i:
            factors.append(i)
            n //= i
    if n != 1: factors.append(n)
    return factors
factordict = lambda n: Counter(factorint(n))

# endregion

# region main

if __name__ == "__main__":
    main()

# endregion


# endregion

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])
dist = [-1]*(n+1)
dist[1] = 0
while que:
    q = que.popleft()
    d = dist[q]
    for nq in G[q]:
        let = copy.deepcopy(letu[q])
        if dist[nq] != -1: #seen配列としても使う。seenないと閉路でWA
            continue
        dist[nq] = d + 1
        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
import numpy as np
sys.setrecursionlimit(10**8)
input = sys.stdin.readline


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


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


def dfs(s, b, lis, ansl, lines, aa):
    a = aa[s]
    idx = np.searchsorted(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 = 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

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

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


if __name__ == "__main__":
    main()