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 sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n = int(input())
aa = {}
j = 0
for i in [int(i) for i in input().split()]:
    if i in aa:
        aa[i].append(j)
    else:
        aa[i] = [j]
    j += 1
a = [0] * n
k = 1
for i in sorted(list(aa)):
    for j in aa[i]:
        a[j] = k
    k += 1


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.b[r - 1])
            if l & 1:
                s = self.func(s, self.b[r - 1])
                l += 1
            l >>= 1
            r >>= 1
        return s


e = [[] for _ in range(n)]
for _ in range(n - 1):
    aa, bb = [int(i) - 1 for i in input().split()]
    e[aa].append(bb)
    e[bb].append(aa)
seg = SegmentTree([0] * (max(a)+10), max, 0)
ans1 = [0] * n
ans1[0] = 1
ans2 = [0] * n
ans2[0] = 1


def dfs(i=0, r=-1):

    y = seg.get_segment(0, a[i])
    ans1[i] = y + 1
    ans2[i] = max(ans2[r], ans1[i])

    be = seg.get_item(a[i])
    seg.update_func(a[i], ans1[i])
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)
    seg.update(a[i], be)


dfs()
for i in ans2:
    print(i)

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 = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    dist = [-1]*N
    dist[0] = 0
    dp[0] = [A[0]]
    B[0] = [A[0]]
    queue = deque([0])
    while queue:
        now = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            queue.append(i)
            dp[i] += dp[now]
            if A[i] > dp[i][-1]:
                dp[i].append(A[i])
            else:
                dp[i][bisect.bisect_left(dp[i], A[i])] = A[i]

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

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n = int(input())
aa = {}
j = 0
for i in [int(i) for i in input().split()]:
    if i in aa:
        aa[i].append(j)
    else:
        aa[i] = [j]
    j += 1
a = [0] * n
k = 1
for i in sorted(list(aa)):
    for j in aa[i]:
        a[j] = k
    k += 1


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r, i=0):
        j = i - (1 << ((i + 1).bit_length() - 1))+1
        length = 1 << (self.logn - (i + 1).bit_length() + 1)
        ll = j * length
        rr = (j + 1) * length
        if l <= ll and rr <= r:
            return self.b[i]
        elif rr <= l or r <= ll:
            return self.one
        else:
            return self.func(self.get_segment(l, r, i * 2 + 1),
                             self.get_segment(l, r, i * 2 + 2))


e = [[] for _ in range(n)]
for _ in range(n - 1):
    aa, bb = [int(i) - 1 for i in input().split()]
    e[aa].append(bb)
    e[bb].append(aa)
seg = SegmentTree([0] * (max(a)+10), max, 0)
ans1 = [0] * n
ans1[0] = 1
ans2 = [0] * n
ans2[0] = 1


def dfs(i=0, r=-1):

    y = seg.get_segment(0, a[i])
    ans1[i] = y + 1
    ans2[i] = max(ans2[r], ans1[i])

    be = seg.get_item(a[i])
    seg.update_func(a[i], ans1[i])
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)
    seg.update(a[i], be)


dfs()
for i in ans2:
    print(i)

Submission status: Time Limit Exceeded

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

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

arrive = [False] * (N+1)
dp_dict = [deque([]) for _ in range(N)]
dp_dict[0].append(A[0])


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

        else:
            stack.pop()


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

Submission status: Time Limit Exceeded

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

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

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


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

        else:
            stack.pop()


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

Submission status: Time Limit Exceeded

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

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

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


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

        else:
            stack.pop()


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#l=deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え
#start 4:00
N = int(input())
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]



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


#始点sから各頂点への最短距離
d = [[] for i in range(N)]
visited=[False]*N
q=[0]

q=deque(q)

d[0]=[0]

while len(q):
    cp=q.pop()
    a=A[cp]
    #print(cp)
    dp=d[cp]
    visited[cp]=True
    if a>dp[-1]:
        dp.append(a)
    for i in reversed(range(1,len(dp))):
        if dp[i-1]<a:
            dp[i]=min(a,dp[i])
    d[cp]=dp
    for e in edge[cp]:
        if visited[e]==False:
            d[e]=dp.copy()
            q.appendleft(e)
    
    #print(d)
    
for dc in d:
    print(len(dc)-1)
#print(d[4])

Submission status: Time Limit Exceeded

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

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

ans = [-1] * (N + 1)


def DFS(s, LIS, parent=-1):
    a = A[s - 1]
    if not LIS or a > LIS[-1]:
        LIS.append(a)
    else:
        i = bisect.bisect_left(LIS, a)
        LIS[i] = a
    ans[s] = len(LIS)
    for t in edge[s]:
        if t == parent:
            continue
        DFS(t, LIS[:], s)
    return


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

Submission status: Time Limit Exceeded

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

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

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

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

        else:
            stack.pop()


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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import bisect

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

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

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

        else:
            stack.pop()


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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import bisect

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

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

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

        else:
            stack.pop()


dfs(1)
ans[1] = 1

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

Submission status: Time Limit Exceeded

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

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

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

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

        else:
            stack.pop()


dfs(1)
ans[1] = 1

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bisect
import sys
sys.setrecursionlimit(10**9)

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

ans = [0]*N
def dfs(t,f,l):
    res = 0
    i = bisect(l,a[t])
    if len(l)==i:
        l.append(a[t])
    else:
        res = [i,l[i]]
        l[i]=a[t]
    ans[t] = len(l)
    for v in g[t]:
        if v != f:
            back = dfs(v,t,l)
            if back:
                l[back[0]] = back[1]
            else:
                l.pop()
    return res
dfs(0,0,[])
for i in range(N):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [tuple([int(x) for x in input().split()]) for _ in range(n)]

n=n0()
a=[0]
a.extend(n1())
s=n3(n-1)

import networkx as nx

G = nx.Graph()
G.add_edges_from(s)

last_node=[[0,0,0] for i in range(0,n+1)] #頂点名、パスの前の頂点、パスの長さ
for i in range(2,n+1):
    path=nx.dijkstra_path(G,1,i)
    last_node[i]=[i,path[-2],len(path)]

last_node.sort(key=lambda x:x[2])

info={i:[0,0] for i in range(1,n+1)} #現在の最長列、今までの最長列
info[1]=[1,1]
for line in last_node[2:]:
    now=line[0]
    last=line[1]
    if a[last]<a[now]:
            info[now]=[info[last][0]+1,max(info[last][0]+1,info[last][1]+1)]
    else:
        info[now]=[1,info[last][1]]
for line in info.values():
    print(line[1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from collections import deque
    import sys
    input = sys.stdin.readline

    inf = 1 << 30

    N = int(input())
    *a, = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    ans = [0] * N
    lis = [None for _ in range(N)]
    lis[0] = [inf] * N

    dq = deque([0])

    while dq:
        v = dq.popleft()

        if ans[v]: continue

        i = bisect_left(lis[v], a[v])
        lis[v][i] = a[v]
        ans[v] = bisect_left(lis[v], inf)

        for u in g[v]:
            if ans[u]: continue
            dq.append(u)
            lis[u] = lis[v].copy()

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


if __name__ == '__main__':
    main()

# dp[i]=長さiの増加部分列の末尾としてありえる最小値
# というテーブルを持っておいて、数列を列を前から見ながら二分探索で更新箇所を探す

Submission status: Time Limit Exceeded

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [tuple([int(x) for x in input().split()]) for _ in range(n)]

n=n0()
a=[0]
a.extend(n1())
s=n3(n-1)

import networkx as nx

G = nx.Graph()
G.add_edges_from(s)

info={i:[0,0] for i in range(1,n+1)}
info[1]=[1,1]
for i in range(2,n+1):
    path=nx.dijkstra_path(G,1,i)
    for j in range(1,len(path)):
        if info[path[j]][0]==0:
            if a[path[j-1]]<a[path[j]]:
                info[path[j]]=[info[path[j-1]][0]+1,max(info[path[j-1]][1]+1,info[path[j-1]][0]+1)]
            else:
                info[path[j]]=[1,info[path[j-1]][1]]
for line in info.values():
    print(line[1])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
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)]

def dfs(i, s):
    d[i] = len(s)

    for to in edges[i]:
        if d[to] == -1:
            t = s.copy()
            if t[-1] < a[to]:
                t.append(a[to])
            else:
                t[bisect.bisect_left(t, a[to])] = a[to]

            dfs(to, t)

dfs(0, [a[0]])
for i in range(n):
    print(d[i])

Submission status: Time Limit Exceeded

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

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)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect(dp, 10**18) - 1
    for i in range(n):
        if dp[i] == "inf":
            ansl[pos] = i
            break
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline


def eular_tour(tree: list, root: int):
    """根をrootとしたときの頂点に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    res = []
    visited = [False] * n
    visited[root] = True
    q = deque([root])
    while q:
        pos = q.pop()
        res.append(pos)
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            else:
                visited[next_pos] = True
                q.append(pos)
                q.append(next_pos)
    return res


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

tree = [[] for i in range(n)]
for aa, b in info:
    aa -= 1
    b -= 1
    tree[aa].append(b)
    tree[b].append(aa)

res = eular_tour(tree, 0)

array_ind = [0]
lis_array = [a[0]]
ans = [0] * n
ans[0] = 1

# (-1, -1): remove array
# (pos, val): change array
stack1 = []
stack2 = []
for ind in res[1:]:
    if len(array_ind) <= 1 or array_ind[-2] != ind:
        val = a[ind]
        array_ind.append(ind)
        if val > lis_array[-1]:
            lis_array.append(val)
            stack1.append(-1)
            stack2.append(-1)
        else:
            pos = bisect_left(lis_array, val)
            stack1.append(pos)
            stack2.append(lis_array[pos])
            lis_array[pos] = val
        ans[ind] = len(lis_array)
    else:
        del array_ind[-1]
        pos = stack1.pop()
        val = stack2.pop()
        if pos == -1:
            del lis_array[-1]
        else:
            lis_array[pos] = val

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

Submission status: Time Limit Exceeded

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

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)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


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


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

Submission status: Time Limit Exceeded

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

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)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


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


dfs(0, dp)
flag = False
for i in range(n):
    print(ansl[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)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


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


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from bisect import bisect_left, bisect_right


def eular_tour(tree: list, root: int):
    """根をrootとしたときの頂点に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    res = []
    begin = [-1] * n
    end = [-1] * n
    visited = [False] * n
    visited[root] = True
    q = deque([root])
    while q:
        pos = q.pop()
        res.append(pos)
        end[pos] = len(res)
        if begin[pos] == -1:
            begin[pos] = len(res) - 1
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            else:
                visited[next_pos] = True
                q.append(pos)
                q.append(next_pos)
    return res, begin, end


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

tree = [[] for i in range(n)]
for aa, b in info:
    aa -= 1
    b -= 1
    tree[aa].append(b)
    tree[b].append(aa)

res, _, _ = eular_tour(tree, 0)

array_ind = [0]
array_val = [a[0]]
lis_array = [a[0]]
ans = [0] * n
ans[0] = 1

# (-1, -1): remove array
# (pos, val): change array
stack = []
for ind in res[1:]:
    if len(array_ind) <= 1 or array_ind[-2] != ind:
        val = a[ind]
        array_ind.append(ind)
        array_val.append(val)
        if val > lis_array[-1]:
             lis_array.append(val)
             stack.append((-1, -1))
        else:
            pos = bisect_left(lis_array, val)
            stack.append((pos, lis_array[pos]))
            lis_array[pos] = val
        ans[ind] = len(lis_array)
    else:
        del array_ind[-1]
        del array_val[-1]
        pos, val = stack.pop()
        if pos == -1:
            del lis_array[-1]
        else:
            lis_array[pos] = val
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)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1

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


dfs(0, dp)
flag = False
for i in range(n):
    print(ansl[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)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1

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


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

Submission status: Time Limit Exceeded

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

def dfs(v,l,tr):
  ans[v]=l
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      pos=bisect.bisect_left(tr,arr[u])
      if pos==l:
        dfs(u,l+1,tr+[arr[u]])
      elif tr[pos]==arr[u]:
        dfs(u,l,tr)
      else:
        dfs(u,l,tr[:pos]+[arr[u]]+tr[pos+1:])

n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dfs(1,1,[arr[1]])
for i in range(1,n+1):
  print(ans[i])

Submission status: Time Limit Exceeded

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

d = [-1 for _ in range(n)]

def dfs(i, s):
    d[i] = len(s)

    for to in edges[i]:
        if d[to] == -1:
            t = s.copy()
            if t[-1] < a[to]:
                t.append(a[to])
            else:
                t[bisect.bisect_left(t, a[to])] = a[to]

            dfs(to, t)

dfs(0, [a[0]])
for i in range(n):
    print(d[i])