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 .

Solution (Python):
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()

Solution (Python):
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


q = deque([(0, 0)])  
while q:
    u, p = q.pop()

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

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

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

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

print(*ans)

Solution (Python):

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)

Solution (Python):

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)

Solution (Python):
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)  
    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)

Solution (Python):
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]) 
            old = dp[idx]
            dp[idx] = A[v]
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp[idx] = old
        

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


if __name__ == "__main__":
    main()

Solution (Python):
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]) 
            old = dp[idx]
            dp[idx] = A[v]
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp[idx] = old
        

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


if __name__ == "__main__":
    main()

Solution (Python):
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')

Solution (Python):
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))))

Solution (Python):


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 = [float('inf')] * n

lislen = [0] * n  
backup = [None] * n


stack = [(0, 0)]  
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])  
        backup[u] = (l, lis[l])  
        lis[l] = a[u]  
        lislen[u] = bisect_left(lis, float('inf'))  
        stack.append((None, u))  
        for v in adj[u]:
            if v != p:
                stack.append((u, v))

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

Solution (Python):


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 = [float('inf')] * n

lislen = [0] * n  
backup = [None] * n


stack = [(0, 0)]  
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])  
        backup[u] = (l, lis[l])  
        lis[l] = a[u]  
        lislen[u] = bisect_left(lis, float('inf'))  
        stack.append((None, u))  
        for v in adj[u]:
            if v != p:
                stack.append((u, v))

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

Solution (Python):
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')

Solution (Python):
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")

Solution (Python):
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")

Solution (Python):
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

from collections import deque 



from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


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




N = int(input())







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)



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)
    
    for ne in edge[e]:
        if not visited[ne]:
            dfs(ne)
            pi,px=q.pop()
            dp[pi]=px


dfs(0)
    
    
for x in ans:
    print(x)

Solution (Python):
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

from collections import deque 



from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


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




N = int(input())







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)



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)
    
    for ne in edge[e]:
        if not visited[ne]:
            dfs(ne)
            pi,px=q.pop()
            dp[pi]=px


dfs(0)
    
    
for x in ans:
    print(x)

Solution (Python):
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)
    
    LIS[i] = v
    return


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

Solution (Python):
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')

Solution (Python):
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])

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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

Solution (Python):

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