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):
from bisect import bisect_left
INF = 10 ** 12
n = int(input())
a = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u - 1].append(v - 1)
    g[v - 1].append(u - 1)
dp = [INF] * n
k = [None] * n
ans = [0] * n
s = [0]
while s:
    p = s.pop()
    if k[p] == None:
        s.append(p)
        idx = bisect_left(dp, a[p])
        k[p] = (idx, dp[idx])
        dp[idx] = a[p]
        ans[p] = bisect_left(dp, INF)
        for node in g[p]:
            if k[node] == None:
                s.append(node)
    else:
        idx, x = k[p]
        dp[idx] = x
for x in ans:
    print(x)

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    X[x].append(y)
    X[y].append(x)

def EulerTour(n, X, i0):
    def bl(k):
        l, r = -1, n
        while r - l > 1:
            m = (l + r) // 2
            if L[m][-1] < k:
                l = m
            else:
                r = m
        return l + 1

    inf = 1 << 30
    P = [-1] * n
    Q = [~i0, i0]
    ANS = [0] * n
    L = [[inf] for _ in range(n)]
    I = [0] * n
    while Q:
        i = Q.pop()
        if i < 0:
            i = ~i
            L[I[i]].pop()
            continue
        if i >= 0:
            k = A[i]
            b = bl(k)
            L[b].append(k)
            I[i] = b
            ANS[i] = bl(inf)
        for a in X[i][::-1]:
            if a != P[i]:
                P[a] = i
                for k in range(len(X[a])):
                    if X[a][k] == i:
                        del X[a][k]
                        break
                Q.append(~a)
                Q.append(a)
    return ANS

print("\n".join(map(str, EulerTour(N, X, 0))))

Solution (Python):
import sys,bisect
input = sys.stdin.readline

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

ans = [1]*n

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

root = 0
chi = [[] for i in range(n)]
par = [-1]*n
used = [False]*n
tank = [0]

while tank:
    q = tank.pop()
    used[q] = True
    for e in edge[q]:
        if not used[e]:
            chi[q].append(e)
            tank.append(e)
            par[e] = q

tank = [root]

idx = dict()
val = dict()
dp = [10**10]*n

eulerNum = -1

while tank:
    q = tank.pop()
    if q >= 0:
        
        num = a[q]
        kk = bisect.bisect_left(dp,num)
        
        val[q] = dp[kk]
        idx[q] = kk
        dp[kk] = num
        ans[q] = bisect.bisect_left(dp,10**10)

        eulerNum += 1
        tank.append(~q)
        for ch in chi[q]:
            tank.append(ch)
    else:
        if ~q != root:
            if dp[idx[~q]] == a[~q]:
                dp[idx[~q]] = val[~q]
                eulerNum += 1

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

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


ans = [0]*n
def dfs(now,parent,LIS):
    w = bisect(LIS,a[now])
    if w > 0 and LIS[w-1] == a[now]:
        flag = -2
    elif 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 == -2:
        return
    elif flag == -1:
        LIS.pop()
    else:
        LIS[w] = record
    return


















dfs(0,-1,[])
print('\n'.join(str(i) for i in ans))

Solution (Python):
def examA():
    K = I()
    A, B = LI()
    for i in range(A,B+1):
        if i%K==0:
            print("OK")
            return
    print("NG")
    return

def examB():
    X = I()
    now = 100
    ans = 0
    while(now<X):
        ans += 1
        now += now//100
    print(ans)
    return

def examC():
    N, M, Q = LI()

    ans = 0
    print(ans)
    return

def examD():
    A, B, N = LI()
    if N>=B-1:
        ans = (A*(B-1))//B
    else:
        ans = (A*N)//B
    print(ans)
    return

def examE():
    N, M = LI()
    ans = []
    if N%2==1:
        for i in range(N // 2):
            ans.append((i + 1, N - i))
    else:
        flag = False
        for i in range(N // 2):
            if N-i-(i+1)<=N//2:
                flag = True
            if flag:
                ans.append((i+1,N-i-1))
            else:
                ans.append((i + 1, N - i))
    
    for v in ans[:M]:
        print(" ".join(map(str,v)))
    return

def examF():
    N = I()
    A = LI()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        u, v = LI()
        u -= 1; v -= 1
        V[u].append(v)
        V[v].append(u)
    dp = [-1]*N
    dp[0] = 1
    LIS = deque()
    LIS.append(A[0])
    def dfs(s):
        
        for i in V[s]:
            if dp[i]!=-1:
                continue
            flag = []
            if A[i] > LIS[-1]:
                LIS.append(A[i])
                flag = False
            else:
                flag = [bisect.bisect_left(LIS, A[i]),LIS[bisect.bisect_left(LIS, A[i])]]
                LIS[flag[0]] = A[i]
            dp[i] = len(LIS)
            dfs(i)
            
            if not flag:
                LIS.pop()
            else:
                LIS[flag[0]] = flag[1]
        return
    dfs(0)
    ans = dp
    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read

n = int(input())
a = [int(i) for i in readline().split()]
m = map(int,read().split())

g = [[] for _ in range(n)]
for i,j in zip(m,m):
    g[i-1].append(j-1)
    g[j-1].append(i-1)

INF = 10**9

q = [~0,0]
dp = [INF]*n
ans = [0]*n
val = 0
idx = [-1]*n
old = [-1]*n
parent = [-1]*n

ss = 0
from bisect import bisect_left
while q:
    v = q.pop()
    if v >= 0:
        iv = idx[v] = bisect_left(dp,a[v])
        x = old[v] = dp[idx[v]]
        if x == INF: val += 1
        ans[v] = val

        dp[iv] = a[v]
        for c in g[v]:
            if c != parent[v]:
                parent[c] = v            
                q.append(~c)
                q.append(c)
    else:
        v = ~v
        x = dp[idx[v]] = old[v]
        if x == INF: val -= 1
    

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

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
A = [0] + list(map(int,input().split()))
C = [list(map(int,input().split())) for i in range(n-1)]


sys.setrecursionlimit(10**5 + 5)  


M = [[] for i in range(n+1)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])



V = [0] * (n+1)

ANS = [0] * (n+1)

R = [10**10] * (n+5)

import bisect

R[0] = A[1]
ANS[1] = 1

def des(x):
    
    V[x] = 1
    


    for i in M[x]:
        if V[i] == 0:
            
            
            V[i] = 1
            ind = bisect.bisect_left(R, A[i])
            ma = R[ind]
            R[ind] = A[i]
            ANS[i] = bisect.bisect_left(R, 10**10-1)
            des(i)
            R[ind] = ma

    
    
    

des(1)

for i in range(1, len(ANS)):
    print(ANS[i])

Solution (Python):
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
a = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ 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
dp = [INF for _ in range(n)]
ans = [0 for _ in range(n)]

def dfs(x, p):
	ans[x] = bisect_left(dp, INF)
	for v in adj[x]:
		if v == p:
			continue
		ind = bisect_left(dp, a[v])
		pres = dp[ind]
		dp[ind] = a[v]
		dfs(v, x)
		dp[ind] = pres
	return

dp[0] = a[0]
dfs(0, -1)
print(*ans, sep="\n")

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

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]

seg = SegTree(N + 1, max, 0, X_commutative=True)
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)

for e in tour:
    if e > 0:
        LIS[e] = max(LIS[e], LIS[parent[e]])

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

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


ans = [0]*n
def dfs(now,parent,LIS):
    w = bisect(LIS,a[now])
    if w > 0 and LIS[w-1] == a[now]:
        flag = -2
    elif 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 == -2:
        return
    elif flag == -1:
        LIS.pop()
    else:
        LIS[w] = record
    return


















dfs(0,-1,[])
print('\n'.join(str(i) for i in ans))

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left

INF = 10**17

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


stack = [0]
ans = [-1]*N
dp = [INF]*(N+1)
to_rev = [(-1, -1) for _ in range(N)]
while stack:
    p = stack.pop()
    if p >= 0:
        ind = bisect_left(dp, A[p])
        to_rev[p] = (ind, dp[ind])
        dp[ind] = A[p]
        ans[p] = bisect_left(dp, INF)
        stack.append(~p)
        for np in graph[p]:
            if ans[np] == -1:
                stack.append(np)
    else:
        p = ~p
        ind, score = to_rev[p]
        dp[ind] = score

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

Solution (Python):
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):
    
    ans[v] = dp_len
    for v_next in graph[v]:
        if v_next == v_p:
            continue

        
        if a[v_next] > dp[dp_len - 1]:
            past = dp[dp_len]
            dp[dp_len] = a[v_next]
            dfs(v_next, v, dp_len + 1)
            dp[dp_len] = past
        else:
            idx = bisect_left(dp, a[v_next])
            
            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')

Solution (Python):
import sys
import bisect

sys.setrecursionlimit(10**7)
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
printn = lambda x: print(*x, sep='\n')

n = ni()
a = nl()
G = [list() for _ in range(n)]

for _ in range(n-1):
    u, v = nm()
    u -= 1; v -= 1
    G[u].append(v)
    G[v].append(u)

dfsl = list()
seen = [False]*n
stack = [0]
par = [-1]*n
while stack:
    v = stack[-1]
    dfsl.append(v)
    if seen[v]:
        stack.pop()
    else:
        seen[v] = True
        for x in G[v]:
            if x == par[v]:
                continue
            par[x] = v
            stack.append(x)

ans = [0]*n
prv = [0]*n
idx = [None]*n
lis = list()
for v in dfsl:
    if idx[v] is None:
        if not lis or lis[-1] < a[v]:
            idx[v] = len(lis)
            prv[v] = -1
            ans[v] = len(lis) + 1
            lis.append(a[v])
        else:
            i = bisect.bisect_left(lis, a[v])
            idx[v] = i
            prv[v] = lis[i]
            ans[v] = len(lis)
            lis[i] = a[v]
    else:
        if prv[v] < 0:
            lis.pop()
        else:
            lis[idx[v]] = prv[v]
printn(ans)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

sys.setrecursionlimit(230000)
import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur], 0, lis+1)
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [999999999999] * (n+2)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)

Solution (Python):

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"))
        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 = [0]*n
    dfs(0,dp)
    for i in ans:
        print(i)
    return


if __name__ == "__main__":
    solve()

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

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