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:
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
        # 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
        return diffs


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

Submission status: Time Limit Exceeded

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

def main():
    input = sys.stdin.buffer.readline

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

    neighbor = {}
    for i in range(n-1):
        u, v = map(int, input().split())
        if u-1 not in neighbor:
            neighbor[u-1] = []
        if v-1 not in neighbor:
            neighbor[v-1] = []
        neighbor[u-1].append(v-1)
        neighbor[v-1].append(u-1)

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

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

        l2 = copy(l)
        j = bisect_left(l2, a[cur])
        if j == len(l2):
            l2.append(a[cur])
        else:
            l2[j] = a[cur]
        ans[cur] = len(l2)

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
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 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, np.array([], dtype=np.int))]

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

        L = len(lis)

        if L == idx:
            lis = np.append(lis, a)
            ansl[s] = L + 1
        else:
            lis[idx] = a
            ansl[s] = L

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

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

def main():
    n = int(input())
    A = list(map(int, input().split()))
    T = [[] for _ in range(n)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        T[u].append(v)
        T[v].append(u)
    L = [0]*n
    INF = 2**31 - 1
    def dfs(v, par, B):
        B[bisect.bisect_left(B, A[v])] = A[v]
        L[v] = bisect.bisect_left(B, INF)
        for nv in T[v]:
            if nv != par:
                dfs(nv, v, B.copy())
    dfs(0, -1, [INF]*n)
    print(*L, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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[s] = len(F[s])


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

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

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


dp = [None] * N

dp[0] = [a[0]]
Q = [0]

while Q:
    u = Q.pop()
    for v in to[u]:
        if dp[v] is not None:
            continue
        dp[v] = [*dp[u]]
        if a[v] > dp[u][-1]:
            dp[v].append(a[v])
        else:
            dp[v][bisect.bisect_left(dp[v], a[v])] = a[v]
        Q.append(v)

for d in dp:
    print(len(d))

Submission status: Time Limit Exceeded

Solution code:
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
sys.setrecursionlimit(10**6)
N=int(input())
A=[0]+list(map(int,input().split()))

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

USE=[0]*(N+1)
USE[1]=1
ANS=[0]*(N+1)

import bisect
def dfs(x,DP):
    #print(x,DP)
    DP=list(DP)
    pos=bisect.bisect_left(DP,A[x])
    #print(pos)
    if pos<len(DP):
        DP[pos]=A[x]
    else:
        DP.append(A[x])
    #print(DP)

    ANS[x]=len(DP)

    for to in E[x]:
        if USE[to]==0:
            USE[to]=1
            dfs(to,tuple(DP))

dfs(1,tuple())

print(*ANS[1:])

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 = [a[0]]
d.append((0,-1,copy(dpinit)))
ansls=[0]*n
ansls[0]=1
while d:
    u,p,dp = d.pop()
    for v in to[u]:
        if v==p:
            continue
        dp2=copy(dp)
        idx=bisect.bisect_left(dp2,a[v])
        if idx<len(dp2):
            dp2[idx]=a[v]
        else:
            dp2.append(a[v])
        ansls[v]=len(dp2)
        d.append((v,u,dp2))

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

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)
        for nx in tree[current]:
            if not visited[nx]:
                LIScp = copy.copy(org)
                dfs(tree, nums, answers, nx, LIScp, visited)

        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
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
sys.setrecursionlimit(10**6)
N=int(input())
A=[0]+list(map(int,input().split()))

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

USE=[0]*(N+1)
USE[1]=1
ANS=[0]*(N+1)

import bisect
def dfs(x,DP):
    #print(x,DP)
    DP=list(DP)
    pos=bisect.bisect_left(DP,A[x])
    #print(pos)
    if pos<len(DP):
        DP[pos]=A[x]
    else:
        DP.append(A[x])
    #print(DP)

    ANS[x]=len(DP)

    for to in E[x]:
        if USE[to]==0:
            USE[to]=1
            dfs(to,tuple(DP))

dfs(1,tuple())

print(*ANS[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF = 2**30
N = int(input())
A = list(map(int, input().split()))
E = []
for i in range(N):
    E.append([])
for i in range(N-1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    E[u].append(v)
    E[v].append(u)

ans = [0] * N
dp = [INF] * (N+10)

def dfs(now, par, len):
    ng = -1
    ok = len+5
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if A[now] <= dp[mid]:
            ok = mid
        else:
            ng = mid
    memo = dp[ok]
    dp[ok] = A[now]

    ng1 = 0
    ok1 = len+5
    while ok1 - ng1 > 1 :
        mid = (ok1 + ng1) // 2
        if dp[mid] == INF:
            ok1 = mid
        else:
            ng1 = mid
    ans[now] = ok1

    for to in E[now]:
        if to == par:
            continue
        dfs(to, now, len+1)
    dp[ok] = memo

dfs(0, -1, 0)

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

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

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)

    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: 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 = [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])
        if idx<len(dp2):
            dp2[idx]=a[v]
        else:
            dp2.append(a[v])
        ansls[v]=len(dp2)
        d.append((v,u,copy(dp2)))

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

Submission status: Time Limit Exceeded

Solution code:
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(len(LIS))


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

edges = {}
for i in range(n-1):
    u,v = map(int,input().split())
    if u not in edges:
        edges[u] = [v]
    else:
        edges[u].append(v)

    if v not in edges:
        edges[v] = [u]
    else:
        edges[v].append(u)

visited = set()
visited.add(1)
buf = [[1,[arr[0]]]]
ans = [1 for i in range(n)]

while True:
    temp = []
    for b in buf:
        for tow in edges[b[0]]:
            if tow not in visited:
                tptp = b[1].copy()
                if arr[tow-1] > tptp[-1]:
                    tptp.append(arr[tow-1])
                else:
                    tptp[bisect.bisect_left(tptp, arr[tow-1])] = arr[tow-1]
                temp.append([tow,tptp])
                ans[tow-1] = len(tptp)
                visited.add(tow)
            else:
                continue
    # print(buf)
    # print(ans)
    buf = temp
    if len(buf) == 0:
        break

for i in range(n):
    print(ans[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]
d = deque([(0, -1, lis)])
ans = [-1] * n

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

    l2 = copy(l)
    j = bisect_left(l2, a[cur])
    if j == len(l2):
        l2.append(a[cur])
    else:
        l2[j] = a[cur]
    ans[cur] = len(l2)

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

        L = len(lis)

        if L == idx:
            lis.append(a)
            ansl[s] = L + 1
        else:
            lis[idx] = a
            ansl[s] = L

        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:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
import numpy as np

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 = np.array([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)
    i = np.searchsorted(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,np.copy(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
sys.setrecursionlimit(10**9)
INF = 2**30
N = int(input())
A = list(map(int, input().split()))
E = []
for i in range(N):
    E.append([])
for i in range(N-1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    E[u].append(v)
    E[v].append(u)

ans = [0] * N
dp = [INF] * (N+10)

def dfs(now, par):
    ng = -1
    ok = N+5
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if A[now] <= dp[mid]:
            ok = mid
        else:
            ng = mid
    memo = dp[ok]
    dp[ok] = A[now]

    ng1 = 0
    ok1 = N+5
    while ok1 - ng1 > 1 :
        mid = (ok1 + ng1) // 2
        if dp[mid] == INF:
            ok1 = mid
        else:
            ng1 = mid
    ans[now] = ok1

    for to in E[now]:
        if to == par:
            continue
        dfs(to, now)
    dp[ok] = memo


dfs(0, -1)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    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 = [-1 for _ in range(n)]
    memo = [[] for _ in range(n)]
    que = deque()
    que.append(0)
    memo[0] = [a[0]]
    d[0] = 1

    while len(que):
        cur = que.popleft()
        for to in edges[cur]:
            if d[to] == -1:
                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])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#MLE注意！0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        c,b = map(int, input().split())
        adj[c-1].append(b-1)
        adj[b-1].append(c-1)

    # 頂点1も含む
    res = [0]*n
    res[0] = 1

    def dfs(v, par, L):
        for nv in adj[v]:
            temp = L[:]
            if nv == par:
                continue
            if a[nv] > temp[-1]:
                temp.append(a[nv])
            else:
                temp[bisect_left(temp, a[nv])] = a[nv]
            res[nv] = len(temp)
            dfs(nv, v, temp)

    L = [a[0]]
    dfs(0, -1, L)
    for i in range(n):
        print(res[i])

if __name__ == '__main__':
    main()