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: Accepted

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)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=LI()
    to=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=LI1()
        to[u].append(v)
        to[v].append(u)
    dp=[0]
    ans=[0]*n

    def dfs(u=0,pu=-1):
        a=aa[u]
        i=bisect_left(dp,a)
        end=(i==len(dp))
        if end:dp.append(a)
        else:
            pre=dp[i]
            dp[i]=a
        ans[u]=len(dp)-1
        for v in to[u]:
            if v==pu:continue
            dfs(v,u)
        if end:dp.pop()
        else:dp[i]=pre

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

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

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

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N

# DFS
q = deque([(0, 0)])  # (current, parent)
while q:
    u, p = q.pop()

    # Roll back
    if p is None:
        i, x = rb[u].pop()
        dp[i] = x
        continue

    # Update dp
    i = bisect_left(dp, A[u])
    rb[u].append((i, dp[i]))
    dp[i] = A[u]

    # Calc ans
    ans[u] = max(i, ans[p])

    # Go to next
    q.append((u, None))
    for v in graph[u]:
        if v == p:
            continue
        q.append((v, u))

print(*ans)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
import bisect

sys.setrecursionlimit(10**7)
n = int(input())
l = list(map(int,input().split()))
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)


ans = [0]*n
ans[0] = 1
dp = [l[0]]

def dfs(now,bef):
    
    change = True
    if l[now] > dp[-1]:
        dp.append(l[now])
    else:
        index = bisect.bisect_left(dp,l[now])
        change = False
        s = dp[index]
        dp[index] = l[now] 
    ans[now] = len(dp)
    
    for nex in e[now]:
        if nex != bef:
            dfs(nex,now)
    if change:
        dp.pop()
    else:
        dp[index] = s 

for i in e[0]:
    dfs(i,0)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if not directed:
            pt[t[i]-1].append(s[i]-1)
    return pt

def euler_tour(pt,N,root):
    S = [(~root,-1),(root,-1)]
    tour = [None]*(2*N)  #ツアー順（2*N-1要素）
    F = [None]*N         #最初の到達時刻
    depth = [0]*N
    count = -1
    while(S):
        v,p = S.pop()
        count += 1
        if v >= 0:
            tour[count] = v
            if not F[v]:
                F[v] = count
            for nv in pt[v][::-1]:
                if nv == p:
                    continue
                depth[nv] = depth[v]+1
                S.append((~nv,v))
                S.append((nv,v))
        else:
            tour[count] = p
    tour.pop()
    return tour

N = I()
a = LI()
u,v = LIR(N-1,2)

pt = edges_to_pt(u,v,N)
tour = euler_tour(pt,N,0)

inf = 10**9+1
dp = [inf]*N
record = []
visited = [False]*N
ans = [0]*N
for v in tour:
    if visited[v]:
        r = record.pop()
        dp[r[0]] = r[1]
    else:
        p = bisect_left(dp,a[v])
        record.append((p,dp[p]))
        dp[p] = a[v]
        pinf = bisect_left(dp,inf)
        ans[v] = pinf
        visited[v] = True

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(2*10**5)
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        repn[u - 1].append(v - 1)
        repn[v - 1].append(u - 1)
    
    length = [0] * (N + 1)
    dp = [-1]

    """
    やはり各頂点でLIS配列を取ると配列コピーの時間がかかってTLEするので、
    配列は唯一つを扱って、DFSからバックするときに配列も元に戻す操作を行いたい
    （ここの実装の仕方がわからなかった）

    これはdfsを再帰で書いた後に復元操作を追記すれば異常に楽に書ける。。。
    """

    def dfs(v, p=N):
        if A[v] > dp[-1]:
            dp.append(A[v])
            length[v] = length[p] + 1
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp.pop()
        else:
            length[v] = length[p]
            idx = bisect_left(dp, A[v]) # bisect_rightだとdpに重複する値を書き込んでしまうのでダメ
            old = dp[idx]
            dp[idx] = A[v]
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp[idx] = old
        #print("v={}, len={}, dp={}".format(v, length[v], dp))

    dfs(0)
    length.pop()
    for ans in length:
        print(ans)
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools,bisect,collections,heapq
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**9+1

N = NI()
a = LI()

root = [[] for _ in range(N)]
for _ in range(N-1):
    u,v = LI()
    root[u-1].append(v-1)
    root[v-1].append(u-1)

lis = [INF for _ in range(N)]
q = []

q.append((0,0,0))
ans = [-1 for _ in range(N)]
while q:
    c,p,v = q.pop()
    if c == 0:
        x = bisect.bisect_left(lis,a[p])
        y = lis[x]
        if y == INF: v +=1
        if y > a[p]: lis[x] = a[p]
        ans[p] = v
        q.append((1,x,y))
        for d in root[p]:
            if ans[d] < 0: q.append((0,d,v))
    else:
        lis[p] = v
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


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


n = int(input())
aa = {}
for j,i in enumerate(map(int,input().split())):
    if i in aa:
        aa[i].append(j)
    else:
        aa[i] = [j]
a = [0] * n
for k,i in enumerate(sorted(list(aa))):
    for j in aa[i]:
        a[j] = 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)+2), 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()
print("\n".join(map(str,(ans2))))

Submission status: Accepted

Solution code:
# F - LIS on Tree

from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n
adj = {u: [] for u 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)

# lis[i] == 長さi+1の増加列の末尾の最小値
lis = [float('inf')] * n

lislen = [0] * n  # lislen[u] == 頂点uまでのLISの長さ
backup = [None] * n

# DFS (with an explicit stack)
stack = [(0, 0)]  # (parent, child)
while len(stack) > 0:
    p, u = stack.pop()
    if p == None:  # 帰りがけ
        l, x = backup[u]
        lis[l] = x  # 復元
    else:  # 行きがけ
        l = bisect_left(lis, a[u])  # a[u]を使って長さl+1のLISを作れる
        backup[u] = (l, lis[l])  # 後で復元するために保存
        lis[l] = a[u]  # 更新
        lislen[u] = bisect_left(lis, float('inf'))  # 現時点のLISの長さ
        stack.append((None, u))  # 帰りがけタスクをpush
        for v in adj[u]:
            if v != p:
                stack.append((u, v))

for u in range(n):
    print(lislen[u])

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**9+1
MOD = 10**9 + 7
DD = ((1,0),(-1,0),(0,1),(0,-1))

N = NI()
a = LI()

root = [[] for _ in range(N)]
for _ in range(N-1):
    u,v = LI()
    root[u-1].append(v-1)
    root[v-1].append(u-1)

lis = [INF for _ in range(N)]
q = []

q.append((0,0,0))
ans = [-1 for _ in range(N)]
while q:
    c,p,v = q.pop()
    if c == 0:
        x = bisect.bisect_left(lis,a[p])
        y = lis[x]
        if y == INF: v +=1
        if y > a[p]: lis[x] = a[p]
        ans[p] = v
        q.append((1,x,y))
        for d in root[p]:
            if ans[d] < 0:
                q.append((0,d,v))
    else:
        lis[p] = v
print(*ans,sep='\n')

Submission status: Accepted

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

from bisect import bisect_left

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

INF = 10 ** 10

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

arrived = [False] * n
arrived[0] = True

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

dp = [INF] * n
dp[0] = a[0]


def dfs(u):
    for v in adj[u]:
        if not arrived[v]:
            arrived[v] = True
            idx = bisect_left(dp, a[v])
            tmp = dp[idx]
            dp[idx] = a[v]
            ans[v] = bisect_left(dp, INF)
            dfs(v)
            dp[idx] = tmp


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

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
A = tuple(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
 
ans = [-1] * (N + 1)
inf = 10**18
LIS = [inf] * (N + 1)
 
def DFS(s, parent=0):
    a = A[s - 1]
    i = bisect.bisect_left(LIS, a)
    v = LIS[i]
    LIS[i] = a
    ans[s] = bisect.bisect_left(LIS, inf)
    for t in graph[s]:
        if t == parent:
            continue
        DFS(t, s)
    LIS[i] = v
    return
 
DFS(1)
print(*ans[1:], sep="\n")

Submission status: Accepted

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から各頂点への最短距離
inf=10**10
dp = [inf]*N
visited=[False]*N
q=[]
q=deque(q)
ans=[0]*N

def dfs(e):
    visited[e]=True
    a=A[e]
    ci=bisect_left(dp,a)
    q.append((ci,dp[ci]))
    dp[ci]=a
    ans[e]=bisect_left(dp,inf)
    #print(edge[e])
    for ne in edge[e]:
        if not visited[ne]:
            dfs(ne)
            pi,px=q.pop()
            dp[pi]=px


dfs(0)
    #print(d)
    
for x in ans:
    print(x)
#print(d[4])

Submission status: Accepted

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)
inf = 10**18
LIS = [inf] * (N + 10)


def DFS(s, parent=0):
    a = A[s - 1]
    i = bisect.bisect_left(LIS, a)
    v = LIS[i]
    LIS[i] = a
    ans[s] = bisect.bisect_left(LIS, inf)
    for t in edge[s]:
        if t == parent:
            continue
        DFS(t, s)
    # 頂点sでの結果をもとに戻す
    LIS[i] = v
    return


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

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))

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


ans = [0] * N
ans[0] = 1
INF = 10**10
dp = [INF] * N
dp[0] = A[0]
def dfs(node, par, n):
  global ans
  global dp
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    _idx, _num = idx, dp[idx] # 巻き戻し用に退避
    dp[idx] = num
    _n = max(n, idx + 1)
    ans[child] = _n
    dfs(child, node, _n)
    # 巻き戻し
    dp[_idx] = _num

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import sys

sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(buff_readline())


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


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

    ans = [-1] * (N+1)
    ans[1] = 1
    dp = [INF] * (N+1)
    dp[0] = A[1]

    def dfs(u, p):
        for v in g[u]:
            if v == p:
                continue

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            ans[v] = bisect.bisect_left(dp, INF)
            dfs(v, u)
            dp[i] = b

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import sys

sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(buff_readline())


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


def read_float():
    return float(buff_readline())


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


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


def read_str_n():
    return readline().strip().split()


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


def mt(f):
    import time

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

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

    return wrap





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

    ans = [-1] * (N+1)
    ans[1] = 1
    dp = [INF] * (N+1)
    dp[0] = A[1]

    def dfs(u, p):
        for v in g[u]:
            if v == p:
                continue

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            ans[v] = bisect.bisect_left(dp, INF)
            dfs(v, u)
            dp[i] = b

    dfs(1, 0)

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import sys

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


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap





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

    def dfs(u, p, dp):
        for v in g[u]:
            if v == p:
                continue

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            ans[v] = bisect.bisect_left(dp, INF)
            dfs(v, u, dp)
            dp[i] = b
    dp = [INF] * (N+1)
    dp[0] = A[1]
    dfs(1, 0, dp)

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import sys

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


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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


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

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

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

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            ans[v] = bisect.bisect_left(dp, INF)
            dfs(v, u, dp)
            dp[i] = b
    dp = [INF] * (N+1)
    dp[0] = A[1]
    dfs(1, 0, dp)

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import sys

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


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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


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

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

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

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            ans[v] = bisect.bisect_left(dp, INF)
            dfs(v, u, dp)
            dp[i] = b
    dp = [INF] * (N+1)
    dp[0] = A[1]
    dfs(1, 0, dp)

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import sys

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


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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


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

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

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

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            ans[v] = bisect.bisect_left(dp, INF)
            dfs(v, u, dp)
            dp[i] = b
    dp = [INF] * (N+1)
    dp[0] = A[1]
    dfs(1, 0, dp)

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import sys

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


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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


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

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

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

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            ans[v] = bisect.bisect_left(dp, INF)
            dfs(v, u, dp)
            dp[i] = b
    dp = [INF] * (N+2)
    dp[0] = A[1]
    # dp[1] = A[1]
    dfs(1, 0, dp)

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

inf = 10**10
lis = [inf] * n
inf_ind = 0
parent = [-1]*(n+1)
operate = [0] * (n+1)
ans = [-1]*(n+1)
d = deque()
d.append(1)
while(d):
    now = d.popleft()
    if(operate[now]==0):
        p = parent[now]
        if(p!=-1):
            d.appendleft(now)
        for child in links[now]:
            if(child != p):
                parent[child] = now
                d.appendleft(child)

        a_now = a[now-1]
        ind = bisect.bisect_left(lis,a_now)
        operate[now] = (ind,lis[ind],a_now)
        lis[ind] = a_now
        if(inf_ind == ind):
            inf_ind += 1
        ans[now] = inf_ind
    else:
        ind,before,after = operate[now]
        lis[ind] = before
        if(before == inf):
            inf_ind -= 1
    # print(lis)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import sys

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


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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


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

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

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

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

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

    # return ans[:N]


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


if __name__ == '__main__':
    main()