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: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

import sys
sys.setrecursionlimit(10**7)

class RangeMinimumQuery:
    def __init__(self, n, F=min, e=float("inf"), fill=None):
        self.n0 = 2**(n-1).bit_length()
        self.F = F
        self.e = e
        if fill is None:
            fill = e
        self.data = [fill]*(2*self.n0)

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.e
        while l < r:
            if r&1:
                r -= 1
                res = self.F(res, self.data[r-1])
            if l&1:
                res = self.F(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i:
            i = ~-i//2
            self.data[i] = self.F(self.data[2*i+1], self.data[2*i+2])


n = int(input())
a = list(map(int, input().split()))
d = {j:i for i,j in enumerate(sorted(set(a)))}
m = len(d)
a = [d[i] for i in a]

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

RMQ = RangeMinimumQuery(m, max, 0)
ans = [0]*n
def dfs(cur, prev):
    ai = a[cur]
    now = RMQ.query(ai, ai+1)
    nxt = max(RMQ.query(0, ai)+1, now)
    ans[cur] = nxt
    RMQ.update(ai, nxt)
    for to in G[cur]:
        if to != prev:
            dfs(to, cur)
    RMQ.update(ai, now)
dfs(0,-1)

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

Submission status: Wrong Answer

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

####
from bisect import bisect_left
def solve(N, A, graph):
    ans = [0] * N
    cur = [[] for _ in xrange(N)]
    info = [None] * N
    VISIT, DO = 0, 1
    stack = [[0,-1, 0]]
    while stack:
        node, par, cmd = stack.pop()
        x = A[node]
        if cmd == VISIT:
            if par >= 0:
                lo = 0
                hi = N
                while lo < hi:
                    mi = lo + hi >> 1
                    if not cur[mi]:
                        hi = mi
                    elif cur[mi][-1] < x:
                        lo = mi + 1
                    else:
                        hi = mi
                i = lo
                cur[i].append(x)
                info[node] = i
                if i+1 > ans[node]:
                    ans[node] = i + 1

            stack.append([node, par, DO])
            for nei in graph[node]:
                if nei != par:
                    stack.append([nei, node, VISIT])
        else:
            if par >= 0:
                i = info[node]
                cur[i].pop()
    return [x+1 for x in ans]

N = rri()
A = rrm()
graph = [[] for _ in xrange(N)]
for _ in xrange(N - 1):
    u, v = rrm()
    u -= 1; v -= 1
    graph[u].append(v)
    graph[v].append(u)

for x in solve(N, A, graph):
    print x

Submission status: Wrong Answer

Solution code:
import sys
from copy import copy
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

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

ans = [0] * n
dp = [float('inf')] * n
dp[0] = a[0]


def dfs(v, v_p, dp_len):
    # print(v, v_p, dp)
    ans[v] = dp_len
    for v_next in graph[v]:
        if v_next == v_p:
            continue

        # print(dp)
        if a[v_next] > dp[dp_len - 1]:
            dp[dp_len] = a[v_next]
            dfs(v_next, v, dp_len + 1)
        else:
            idx = bisect_left(dp, a[v_next])
            # always idx < dp_len
            past = dp[idx]
            dp[idx] = a[v_next]
            dfs(v_next, v, dp_len)
            dp[idx] = past


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

def LIS(arr):
    from bisect import bisect_left
    INF = 10 ** 15
    
    len_arr = len(arr)
    LIS = [INF for i in range(len_arr + 1)]
  
    for a in arr:
      LIS_i = bisect_left(LIS, a)
      LIS[LIS_i] = min(LIS[LIS_i], a)

    for i in range(len_arr + 1):
      if LIS[i] == INF:
        return i

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

graph = [[] for _ in range(N + 1)]
for uv in UV:
    u, v = uv
    graph[u].append(v)
    graph[v].append(u)
#print(graph)

answer = [0] * (N + 1)
def dfs(prev, n, lst):
    answer[n] = LIS(lst)
    for g in graph[n]:
        if g != prev:
            dfs(n, g, lst + [A[g]])

dfs(-1, 1, [A[0]])

for a in answer[1:]:
    print(a)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class SegTree:
    def __init__(self, N, X_f, X_unit, X_commutative=False):
        self.N = N
        self.X_f = X_f
        self.X_unit = X_unit
        self.X = [self.X_unit] * (N + N)
        if X_commutative:
            self.fold = self._fold_commutative

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

    def _fold_commutative(self, L, R):
        L += self.N
        R += self.N
        v = self.X_unit
        while L < R:
            if L & 1:
                v = self.X_f(v, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                v = self.X_f(v, self.X[R])
            L >>= 1
            R >>= 1
        return v

N = int(readline())
A = (0, ) + tuple(map(int, readline().split()))

seg = SegTree(N + 1, max, 0)

m = map(int, read().split())
U, V = zip(*zip(m, m))

def edges_to_graphdata(A, B, N, M):
    head = [-1] * (N + 1)
    nxt = [0] * (M + M)
    to = [0] * (M + M)
    for i in range(M):
        a = A[i]
        b = B[i]
        nxt[i << 1] = head[a]
        to[i << 1] = b
        head[a] = i << 1
        nxt[i << 1 | 1] = head[b]
        to[i << 1 | 1] = a
        head[b] = i << 1 | 1
    return head, nxt, to

def EulerTour(head, nxt, to, root=1):
    N = len(head) - 1
    parent = [0] * (N + 1)
    ind_L = [0] * (N + 1)
    ind_R = [0] * (N + 1)
    i = -1
    tour = []
    stack = [-root, root]
    stack[0] = -root
    stack[1] = root
    while stack:
        v = stack.pop()
        tour.append(v)
        i += 1
        if v > 0:
            ind_L[v] = i
            p = parent[v]
            k = head[v]
            while k != -1:
                w = to[k]
                if w == p:
                    k = nxt[k]
                    continue
                parent[w] = v
                stack.append(-w)
                stack.append(w)
                k = nxt[k]
        else:
            ind_R[-v] = i
    return tour, ind_L, ind_R, parent

tour, ind_L, ind_R, parent = EulerTour(*edges_to_graphdata(U, V, N, N - 1))

depth = [0] * (N + 1)
d = 0
for e in tour:
    d += 1 if e > 0 else -1
    if e > 0:
        depth[e] = d

A = [x * (N + N + 10) - d for x, d in zip(A, depth)]
A_unique = sorted(A)
A_rank = [bisect_left(A_unique, x) for x in A]

LIS = [0] * (N + 1)
for e in tour:
    if e > 0:
        i = A_rank[e]
        LIS[e] = seg.fold(0, i+1) + 1
        seg.set_val(i, LIS[e])
    else:
        i = A_rank[-e]
        seg.set_val(i, 0)

print('\n'.join(map(str, LIS[1:])))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
a = list(map(int,input().split()))
ans = [0]*(n)
ki = [[]for i in range(n)]
dp = [0]*n
def dfs(now,last= -1):
    nowp = a[now]
    for next in ki[now]:
        if next == last:continue
        if a[next] > nowp:dp[next] = dp[now]+1
        else:dp[next] = dp[now]
        dfs(next,now)
for i in range(n-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    ki[u].append(v)
    ki[v].append(u)
dp[0] = 1
dfs(0)
print(*dp)

Submission status: Wrong Answer

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

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

# parent = [-1]*n
ans = [0]*n
def dfs(now,parent,LIS):
    w = bisect(LIS,a[now])
    if w == len(LIS):
        flag = -1
        LIS.append(a[now])
    else:
        flag = w
        record = LIS[w]
        LIS[w] = a[now]
    ans[now] = len(LIS)
    for nxt in path[now]:
        if nxt == parent:continue
        dfs(nxt,now,LIS)
    if flag == -1:
        LIS.pop()
    else:
        LIS[w] = record
    return
# stack = [0]
# LIS = [[] for _ in range(n)]
# while stack:
#     p = stack.pop()
#     if p == 0:
#         LIS[p] = [a[p]]
#     else:
#         parray = LIS[parent[p]].copy()
#         nxt = bisect(parray,a[p])
#         if nxt == len(parray):
#             LIS[p] = parray + [a[p]]
#         else:
#             parray[nxt] = a[p]
#             LIS[p] = parray
#     for to in path[p]:
#         if to == parent[p]:continue
#         parent[to] = p
#         stack.append(to)
dfs(0,-1,[])
print('\n'.join(str(i) for i in ans))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class SegTree:
    def __init__(self, N, X_f, X_unit, X_commutative=False):
        self.N = N
        self.X_f = X_f
        self.X_unit = X_unit
        self.X = [self.X_unit] * (N + N)
        if X_commutative:
            self.fold = self._fold_commutative

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

    def _fold_commutative(self, L, R):
        L += self.N
        R += self.N
        v = self.X_unit
        while L < R:
            if L & 1:
                v = self.X_f(v, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                v = self.X_f(v, self.X[R])
            L >>= 1
            R >>= 1
        return v

N = int(readline())
A = (0, ) + tuple(map(int, readline().split()))

seg = SegTree(N + 1, max, 0)

m = map(int, read().split())
U, V = zip(*zip(m, m))

def edges_to_graphdata(A, B, N, M):
    head = [-1] * (N + 1)
    nxt = [0] * (M + M)
    to = [0] * (M + M)
    for i in range(M):
        a = A[i]
        b = B[i]
        nxt[i << 1] = head[a]
        to[i << 1] = b
        head[a] = i << 1
        nxt[i << 1 | 1] = head[b]
        to[i << 1 | 1] = a
        head[b] = i << 1 | 1
    return head, nxt, to

def EulerTour(head, nxt, to, root=1):
    N = len(head) - 1
    parent = [0] * (N + 1)
    ind_L = [0] * (N + 1)
    ind_R = [0] * (N + 1)
    i = -1
    tour = []
    stack = [-root, root]
    stack[0] = -root
    stack[1] = root
    while stack:
        v = stack.pop()
        tour.append(v)
        i += 1
        if v > 0:
            ind_L[v] = i
            p = parent[v]
            k = head[v]
            while k != -1:
                w = to[k]
                if w == p:
                    k = nxt[k]
                    continue
                parent[w] = v
                stack.append(-w)
                stack.append(w)
                k = nxt[k]
        else:
            ind_R[-v] = i
    return tour, ind_L, ind_R, parent

tour, ind_L, ind_R, parent = EulerTour(*edges_to_graphdata(U, V, N, N - 1))

depth = [0] * (N + 1)
d = 0
for e in tour:
    d += 1 if e > 0 else -1
    if e > 0:
        depth[e] = d

A = [x * (N + N) - d for x, d in zip(A, depth)]
A_unique = sorted(A)
A_rank = [bisect_left(A_unique, x) for x in A]

LIS = [0] * (N + 1)
for e in tour:
    if e > 0:
        i = A_rank[e]
        LIS[e] = seg.fold(0, i) + 1
        seg.set_val(i, LIS[e])
    else:
        i = A_rank[-e]
        seg.set_val(i, 0)

print('\n'.join(map(str, LIS[1:])))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
a = list(map(int,input().split()))
ans = [0]*(n)
ki = [[]for i in range(n)]
def dfs(now,last= -1,res = 1):
    nowp = a[now]
    
    ans[now] = res
    for next in ki[now]:
        if next == last:continue
        if a[next] > nowp:dfs(next,now,res+1)
        else:dfs(next,now,res)
for i in range(n-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    ki[u].append(v)
    ki[v].append(u)
dfs(0)
print(*ans)

Submission status: Wrong Answer

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

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

parent = [-1]*n
stack = [0]
LIS = [[] for _ in range(n)]
while stack:
    p = stack.pop()
    if p == 0:
        LIS[p] = [a[p]]
    else:
        parray = LIS[parent[p]]
        nxt = bisect(parray,a[p])
        if nxt == len(parray):
            LIS[p] = parray + [a[p]]
        else:
            parray[nxt] = a[p]
            LIS[p] = parray
    for to in path[p]:
        if to == parent[p]:continue
        parent[to] = p
        stack.append(to)
print('\n'.join(str(len(LIS[i])) for i in range(n)))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x,dp):
        ans[x] = bisect.bisect_left(dp, float("inf"))+1
        for y in v[x]:
            if d[y]:
                d[y] = 0
                i = bisect.bisect_left(dp,a[y])
                p = dp[i]
                dp[i] = a[y]
                dfs(y,dp)
                dp[i] = p

    n = I()
    a = LI()
    v = [[] for i in range(n)]
    for _ in range(n-1):
        x,y = LI()
        x -= 1
        y -= 1
        v[x].append(y)
        v[y].append(x)
    dp = [float("inf")]*n
    dp[0] = a[0]
    d = [1]*n
    d[0] = 0
    ans = [None]*n
    dfs(0,[float("inf")]*n)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

def euler_tour(root, Edge):
    N = len(Edge)
    stack = [root]
    used = [False]*N
    tour = []
    down = []
    dist = [0]*N
    ta = tour.append
    sa = stack.append
    St = [None]*N
    En = [None]*N
    cnt = -1
    while stack:
        cnt += 1
        vn = stack.pop()
        ta(vn)
        
        if St[vn] is None:
            St[vn] = cnt
        En[vn] = cnt
        if used[vn]:
            continue
        for vf in Edge[vn]:
            if used[vf]:
                sa(vf)
            else:
                dist[vf] = 1+dist[vn]
                down.append(vf)
        stack.extend(down)
        down = []
        used[vn] = True
    return St, En, tour, dist





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

_, _, L, dist = euler_tour(0, Edge) 

print(L)
table = [None]*N
table[0] = (-1, -1)
dp = [A[0]]
pre = 0
Ans = [None]*N
for l in L[1:]:
    al = A[l]
    if dist[pre] > dist[l]:
        x, j = table[pre]
        if x == -1:
            dp.pop()
        else:
            dp[j] = x
    else:
        if dp[-1] < al:
            dp.append(al)
            table[l] = (-1, -1)
        else:
            idx = bl(dp, al)
            x = dp[idx]
            dp[idx] = al
            table[l] = (x, idx)
    pre = l
    Ans[l] = len(dp)
        
print('\n'.join(map(str, Ans)))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N=int(input())
*A,=map(int,input().split())
G=[[] for _ in range(N)]
ab = [tuple(map(int,input().split())) for _ in range(N-1)]
for a,b in ab:
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def bfs():
    from collections import deque
    dp = [[] for _ in range(N)]
    dp[0] = [A[0]]
    seen = [0]*N
    todo = deque()
    seen[0]=1
    todo.append(0)
    while todo:
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          idx = bisect_left(dp[a],A[b])
          if idx == len(dp[a]): dp[b] = dp[a]+[A[b]]
          else: dp[b] = [dp[a][i] if i != idx else A[b] for i in range(len(dp[a]))]
          seen[b] = 1
          todo.append(b)
    return dp
  
dp = bfs()
  
print(*[len(dp[i]) for i in range(N)],sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N=int(input())
*A,=map(int,input().split())
G=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def bfs(s):
    from collections import deque
    seen = [0]*N
    d = [0]*N
    prev = [-1]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while todo:
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return d, prev
  
def argsort(arr, reverse=False, shift=20):
    tmp = sorted([arr[i]<<shift | i for i in range(len(arr))],reverse=reverse)
    mask = (1<<shift) - 1
    return [tmp[i] & mask for i in range(len(arr))]
  
d,prev = bfs(0)
order = argsort(d)
dp = [[] for _ in range(N)]
dp[0] = [A[0]]
for v in order:
  if v == 0: continue
  p = prev[v]
  idx = bisect_left(dp[p],A[v])
  if idx == len(dp[p]): dp[v] = dp[p]+[A[v]]
  else: dp[v] = [dp[p][i] if i != idx else A[v] for i in range(len(dp[p]))]
  
print(*[len(dp[i]) for i in range(N)],sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0:
        old = inf
        i = len(LIS)
        LIS.append(x)
    elif x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x
    if inf in LIS:
        a = LIS.index(inf)
    else:
        a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v,prev = -1):
    x = As[v]
    if prev != -1 and x > LIS[prev][-1]:
        l = copy.copy(LIS[prev])
        l.append(x)
        LIS[v] = l
    elif prev != -1:
        l = copy.copy(LIS[prev])
        l[bisect.bisect_left(l, x)] = x
        LIS[v] = l
    else:
        LIS[v] = [x]
    ans_array[v] = len(LIS[v])
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = [[] for i in range(N)]
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        x = As[u]
        if x > LIS[v][-1]:
            LIS[u] = LIS[v] + [x]
        else:
            l = copy.copy(LIS[v])
            l[bisect.bisect_left(l, x)] = x
            LIS[u] = l
        ans_array[u] = len(LIS[u])
        dfs(u,v)

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = [[] for i in range(N)]
LIS[0].append(As[0])
ans_array = [0] * N
ans_array[0] = 1
dfs(0)
for i in range(N):
    print(ans_array[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
from collections import deque
from bisect import bisect_left

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


INF = 10 ** 10
done = [False] * N
done[0] = True
lisdp = [INF] * N
lisdp[0] = A[0]
change = [[-1, INF] for i in range(N)] #index, original
change[0] = [0, INF]
lisl = [0] * N
lisl[0] = 1

def dfs(v):
	for nv in adj[v]:
		if done[nv]:
			continue
		done[nv] = True
		ind = bisect_left(lisdp, A[nv])
		ori = lisdp[ind]
		change[nv] = [ind, ori]
		if ori == INF:
			lisl[nv] = lisl[v] + 1
		else:
			lisl[nv] = lisl[v]
		lisdp[ind] = A[nv]
		dfs(nv)
	lisdp[change[v][0]] = change[v][1]

dfs(0)
for i in range(N):
	print(lisl[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()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 頂点1から頂点kまでの最短パス上
# ルートはO(n)で求められる
N = getN()
A = getList()
query = [getList() for i in range(N - 1)]

dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = query[i]
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

ignore = [0] * N
ignore[0] = 1
lis = [A[0]]
rec = [0] * N
rec[0] = 1

# 行きがけ帰りがけの要領
def dfs(u):
    global lis
    for i in dist[u]:
        if ignore[i] != 1:
            ignore[i] = 1
            ar = deepcopy(lis) # 元の状態をレコード
            if A[i] > ar[-1]:
                lis.append(A[i])
            else:
                lis[bisect_left(ar, A[i])] = A[i]
            rec[i] = len(lis)
            dfs(i)
            lis = deepcopy(ar) # 元に戻す

dfs(0)
for i in rec:
    print(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()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 頂点1から頂点kまでの最短パス上
# ルートはO(n)で求められる
N = getN()
A = getList()
query = [getList() for i in range(N - 1)]

dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = query[i]
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

ignore = [0] * N
ignore[0] = 1
rec = [0] * N
rec[0] = 1

def dfs(u, array):
    for i in dist[u]:
        if ignore[i] != 1:
            ignore[i] = 1
            ar = deepcopy(array)
            if A[i] > ar[-1]:
                ar.append(A[i])
            else:
                ar[bisect_left(ar, A[i])] = A[i]
            rec[i] = len(ar)
            dfs(i, ar)

dfs(0, [A[0]])
for i in rec:
    print(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()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 頂点1から頂点kまでの最短パス上
# ルートはO(n)で求められる
N = getN()
A = getList()
query = [getList() for i in range(N - 1)]

dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = query[i]
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

memo = {}
memo[0] = [A[0]]

pos = deque([0])
ignore = [0] * N
ignore[0] = 1

while len(pos) > 0:
    u = pos.popleft()

    for i in dist[u]:
        if ignore[i] != 1:
            ignore[i] = 1
            ar = deepcopy(memo[u])
            if A[i] > ar[-1]:
                ar.append(A[i])
            else:
                ar[bisect_left(ar, A[i])] = A[i]
            memo[i] = ar
            pos.append(i)

for i in sorted(memo.items()):
    print(len(i[1]))