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, bisect_right
sys.setrecursionlimit(10**6)

N=int(sys.stdin.readline().strip())
A=[None]+map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	
for i in range(N-1):
	u,v=map(int, sys.stdin.readline().split())
	al[u].append(v)
	al[v].append(u)

LIS=[ float("inf") for _ in range(N+1)] 
LIS[0]=float("-inf")
ans={}  

def dfs(cur,par):
    idx=bisect_left(LIS, A[cur])
    old=LIS[idx]    
    LIS[idx]=A[cur]
    ans[cur]=bisect_left(LIS, float("inf"))-1 
    for to in al[cur]:
        if par==to: continue    
        dfs(to,cur)
    LIS[idx]=old    
        
dfs(1,-1)

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

Solution (Python):

import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**6)

N=int(sys.stdin.readline().strip())
A=[None]+map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	
for i in range(N-1):
	u,v=map(int, sys.stdin.readline().split())
	al[u].append(v)
	al[v].append(u)

LIS=[ float("inf") for _ in range(N+1)] 
LIS[0]=float("-inf")
ans={}  

def dfs(cur,par):
    idx=bisect_left(LIS, A[cur])
    old=LIS[idx]    
    LIS[idx]=A[cur]
    ans[cur]=bisect_left(LIS, float("inf"))-1 
    for to in al[cur]:
        if par==to: continue    
        dfs(to,cur)
    LIS[idx]=old    
        
dfs(1,-1)

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

Solution (Python):
from bisect import bisect_left
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    *A,=map(int, input().split())
    G=[[] for _ in range(N)]
    for _ in range(N-1):
        u,v=map(int, input().split())
        u,v=u-1,v-1
        G[u].append(v)
        G[v].append(u)

    INF=10**10
    ans=[0]*N
    l=[INF]*(N+1)
    stk=[(0,0,0)]
    while stk:
        s,a,b=stk.pop()
        if s==0:
            i=bisect_left(l,A[a])
            stk.append((1,i,l[i]))
            l[i]=A[a]
            ans[a]=bisect_left(l,INF)
            for to in G[a]:
                if ans[to]>0: continue
                stk.append((0,to,0))
        else:
            l[a]=b
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**6)

N=int(sys.stdin.readline().strip())
A=[None]+map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	
for i in range(N-1):
	u,v=map(int, sys.stdin.readline().split())
	al[u].append(v)
	al[v].append(u)


LIS=[ float("inf") for _ in range(N+1)] 
LIS[0]=float("-inf")
ans={}  

def dfs(cur,par):
    idx=bisect_left(LIS, A[cur])
    old=LIS[idx]
    LIS[idx]=A[cur]
    ans[cur]=bisect_left(LIS, float("inf"))-1 
    for to in al[cur]:
        if par==to: continue    
        dfs(to,cur)
    LIS[idx]=old
        
dfs(1,-1)

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

Solution (Python):
def f_lis_on_tree(INF=float('inf')):
    
    import sys
    sys.setrecursionlimit(10**7)
    import bisect
    N = int(input())
    A = [0] + [int(i) for i in input().split()]  
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    graph = [[] for _ in range(N + 1)]
    for a, b in Edges:
        graph[a].append(b)
        graph[b].append(a)

    ans = [0] * (N + 1)
    visited = [False] * (N + 1)
    visited[1] = True  
    lis = [INF] * (N + 1)
    changes = []

    def dfs(v):
        
        
        pos = bisect.bisect_left(lis, A[v])
        changes.append((pos, lis[pos]))  
        lis[pos] = A[v]
        ans[v] = bisect.bisect_left(lis, INF)  

        
        for child in graph[v]:
            if not visited[child]:
                visited[child] = True
                dfs(child)

        
        pos, val = changes.pop()
        lis[pos] = val

    dfs(1)
    return ' '.join(map(str, ans[1:]))

print(f_lis_on_tree())

Solution (Python):

import sys
from bisect import bisect_left, bisect_right, insort
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] + lr()  
graph = [[] for _ in range(N+1)]  
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (N+1)  
INF = 10 ** 10
parent = [-1] * (N+1)

def dfs(n):
    """answerのリストを更新してからdfsして、oldで戻す"""
    i = bisect_left(dp, INF)
    answer[n] = i
    for c in graph[n]:
        if c == parent[n]:
            continue
        parent[c] = n
        i = bisect_left(dp, A[c])
        old = dp[i]
        dp[i] = A[c]
        dfs(c)
        dp[i] = old

dp = [INF] * (N+1)
dp[0] = A[1]
dfs(1)
for a in answer[1:]:
    print(a)

Solution (Python):

import sys
from bisect import bisect_left, bisect_right, insort
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] + lr()  
graph = [[] for _ in range(N+1)]  
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (N+1)  
INF = 10 ** 10
parent = [-1] * (N+1)

def dfs(n):
    """arrはLISのリスト、answerのリストを更新してから子にarrを渡す"""
    i = bisect_left(dp, INF)
    answer[n] = i
    for c in graph[n]:
        if c == parent[n]:
            continue
        parent[c] = n
        i = bisect_left(dp, A[c])
        old = dp[i]
        dp[i] = A[c]
        dfs(c)
        dp[i] = old

dp = [INF] * (N+1)
dp[0] = A[1]
dfs(1)
for a in answer[1:]:
    print(a)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.buffer.readline
from bisect import bisect_left
n=int(input())
*a,=map(int,input().split())
dp=[float("inf")]*n
con=[[] for _ in range(n)]
for _ in range(n-1):
	s,t=map(int,input().split())
	con[s-1].append(t-1)
	con[t-1].append(s-1)

ans=[0]*n
def dfs(cur,pre):
	idx=bisect_left(dp,a[cur])
	bef=dp[idx]
	dp[idx]=min(bef,a[cur])
	ans[cur]=bisect_left(dp,float("inf"))
	for nxt in con[cur]:
		if pre!=nxt:
			dfs(nxt,cur)
	dp[idx]=bef
dfs(0,-1)
print("\n".join(map(str,ans)))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)


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


n = int(input())
aa = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

dp = [10 ** 9] * (n + 10)
dp[0] = 0
ans1 = [0] * n
ans2 = [0] * n


def dfs(i=0, r=-1):
    global dp, ans1, ans2
    mi = 0
    ma = n
    while mi != ma:
        mm = (mi + ma) // 2
        if dp[mm] >= aa[i]:
            ma = mm
        else:
            mi = mm + 1

    be = dp[mi]
    dp[mi] = min(dp[mi], aa[i])
    ans1[i] = mi
    ans2[i] = max(ans1[i], ans2[r])

    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)

    dp[mi] = be


dfs()
print("\n".join(map(str, ans2)))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)


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


n = int(input())
aa = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

dp = [10 ** 9] * (n + 10)
dp[0] = 0
ans1 = [0] * n
ans2 = [0] * n


def dfs(i=0, r=-1):
    global dp, ans1, ans2
    mi = 0
    ma = n
    while mi != ma:
        mm = (mi + ma) // 2
        if dp[mm] >= aa[i]:
            ma = mm
        else:
            mi = mm + 1

    be = dp[mi]
    dp[mi] = min(dp[mi], aa[i])
    ans1[i] = mi
    ans2[i] = max(ans1[i], ans2[r])

    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)

    dp[mi] = be


dfs()
print("\n".join(map(str, ans2)))

Solution (Python):

import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        x,y=map(int1,input().split())
        edge[x].append(y)
        edge[y].append(x)
    stack=[(0,1)]
    used=[False]*N
    ans=[0]*N
    dp=[INF]*(N+1)
    dp[0]=0
    dpdp=[]
    prev_l=1
    def dfs(v,l):
        used[v]=True
        index=bisect_right(dp,a[v]-1,hi=l)
        dpdp=(index,dp[index])
        dp[index]=a[v]
        ans[v]=bisect_left(dp,INF,hi=l+1)-1
        for nv in edge[v]:
            if not used[nv]:
                i,x=dfs(nv,l+1)
                dp[i]=x
        return dpdp
    dfs(0,1)
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

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


n = int(input())
A = list(map(int, input().split()))
edges = [[]for _ in range(n)]
for _ in range(n-1):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    edges[u].append(v)
    edges[v].append(u)
INF = 10**18
ans = [INF]*n

def dfs(v, parent):
    x = bisect.bisect_left(lis, A[v])
    prev = lis[x]
    lis[x] = A[v]
    ans[v] = bisect.bisect_left(lis, INF)
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)
    lis[x] = prev


lis = [INF]*n
dfs(0, -1)
for x in ans:
    print(x)

Solution (Python):
import bisect
import collections
import sys

sys.setrecursionlimit(100000000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


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


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())

a = lmi()

adj = collections.defaultdict(set)
uv = llmi(N - 1)
for _u, _v in uv:
    u, v = _u - 1, _v - 1
    adj[u].add(v)
    adj[v].add(u)

trees = {}


class Tree:
    def __init__(self, index, parent_index=-1):
        self.val = a[index]
        self.index = index
        self.parent = parent_index
        self.adj = []
        for v in adj[index]:
            if v == parent_index:
                continue
            self.adj.append(Tree(v, parent_index=self.index))
        self.ans = -1
        trees[index] = self

    def __repr__(self):
        return '{}: {}'.format(self.index, [t.val for t in self.adj])

    def dp(self, current, diffs):
        v = bisect.bisect_left(current, self.val)
        if v >= len(current):
            diffs.append((v, -1))
            current.append(self.val)
        else:
            diffs.append((v, current[v]))
            current[v] = self.val
        self.ans = len(current)
        for child_tree in self.adj:
            diffs = child_tree.dp(current, diffs)
            index, val = diffs.pop()
            if val == -1:
                current.pop()
            else:
                current[index] = val


root = Tree(0)


current = []
diffs = []
self = root

v = bisect.bisect_left(current, self.val)
stack = [(True, root)]
while stack:
    is_start, self = stack.pop()
    if is_start:
        v = bisect.bisect_left(current, self.val)
        if v >= len(current):
            diffs.append((v, -1))
            current.append(self.val)
        else:
            diffs.append((v, current[v]))
            current[v] = self.val
        self.ans = len(current)
        for child_tree in self.adj:
            stack.append((False, child_tree))
            stack.append((True, child_tree))

            
    else:
        index, val = diffs.pop()
        if val == -1:
            current.pop()
        else:
            current[index] = val

for i in range(N):
    print(trees[i].ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    import bisect
    
    N=I()
    A=LI()
    adj=[[]for _ in range(N)]
    
    for i in range(N-1):
        u,v=MI()
        u-=1
        v-=1
        adj[u].append(v)
        adj[v].append(u)
        
    
    
    
    
    
    
    st_ch=[]
    
    
    
    inf=10**10
    dp=[inf]*(N+1)
    
    dp[0]=0
    
    ans=[0]*N


    def EulerTour(n, X, i0=0):
        
        
        P = [-1] * n
        st = [~i0, i0]
        ct = -1
        ET = []
        ET1 = [0] * n
        ET2 = [0] * n
        DE = [0] * n
        de = -1
        while st:
            
            i = st.pop()
            
            
            if i < 0:
                ct += 1
                
                ET.append(P[~i])
                ET2[~i] = ct
                de -= 1
                
                
                num,val=st_ch.pop()
                dp[num]=val
                
                continue
            
            
            if i >= 0:
                ET.append(i)
                ct += 1
                if ET1[i] == 0: ET1[i] = ct
                de += 1
                DE[i] = de
                
                
                num=bisect.bisect_left(dp,A[i])
                st_ch.append((num,dp[num]))
                dp[num]=A[i]
                
                ans_num=bisect.bisect_left(dp,inf)
                ans[i]=ans_num-1
                
                
                
                
            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
                    st.append(~a)
                    st.append(a)
        return (ET, ET1, ET2)
    
    EulerTour(N,adj)
    for i in range(N):
        print(ans[i])
    


                    
                
        
    

main()

Solution (Python):
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

inf = 10 ** 10
lis = [inf] * (N * 2)
s = [1]
vis = [0] * (N + 1)
euler = []
while len(s):
  x = s.pop()
  if x >= 0:
    vis[x] = 1
    euler.append(x)
    for y in e[x]:
      if vis[y]: continue
      s.append(~y)
      s.append(y)
  else: euler.append(x)

rollback = []
res = [0] * (N + 1)
for x in euler:
  if x >= 0:
    y = bl(lis, a[x])
    rollback.append((y, lis[y]))
    lis[y] = a[x]
    res[x] = bl(lis, inf)
  else:
    y, v = rollback.pop()
    lis[y] = v

for r in res[1: ]: print(r)

Solution (Python):
from bisect import bisect_left


def main():
    N = int(input())
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [], 0)]
    history = []
    while len(q):
        cur, prev, lis, depth = q.pop()
        while depth < len(history):
            pos, val = history.pop()
            if val is None:
                lis.pop()
            else:
                lis[pos] = val
        idx = bisect_left(lis, A[cur])
        if idx == len(lis):
            history.append((idx, None))
            lis.append(A[cur])
        else:
            history.append((idx, lis[idx]))
            lis[idx] = A[cur]
        ans[cur] = len(lis)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, lis, depth+1))
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    INF = 10 ** 18
    N = int(rl())
    A = list(map(int, rl().split()))
    graph = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(lambda x: int(x) - 1, rl().split())
        graph[u].append(v)
        graph[v].append(u)
    
    ans = [-1] * N
    stack = [0]
    dp = [INF] * (N + 1)
    rewind = [(-1, -1) for _ in range(N)]
    while stack:
        node = stack.pop()
        if 0 <= node:
            idx = bisect_left(dp, A[node])
            rewind[node] = (idx, dp[idx])
            dp[idx] = A[node]
            ans[node] = bisect_left(dp, INF)
            stack.append(~node)
            for child in graph[node]:
                if ans[child] == -1:
                    stack.append(child)
        else:
            idx, val = rewind[~node]
            dp[idx] = val
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
def resolve():
    n = int(input())
    A = list(map(int,input().split()))
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)

    dp = [INF] * (n + 1)
    dp[0] = -INF
    res = 0
    ans = [None] * n
    change = [None] * n
    stack = [(0, -1)]

    while stack:
        v, p = stack.pop()
        if v >= 0:
            idx = bisect_left(dp, A[v])
            change[v] = (idx, dp[idx])
            res = max(res, idx)
            ans[v] = res
            dp[idx] = A[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            v = ~v
            idx, prev = change[v]
            dp[idx] = prev
            res = ans[p]

    print(*ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
def resolve():
    n = int(input())
    A = list(map(int,input().split()))
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)

    dp = [INF] * (n + 1)
    dp[0] = -INF
    res = 0
    ans = [None] * n
    change = [None] * n
    stack = [(0, -1)]

    while stack:
        v, p = stack.pop()
        if v >= 0:
            idx = bisect_left(dp, A[v])
            change[v] = (idx, dp[idx])
            res = max(res, idx)
            ans[v] = res
            dp[idx] = A[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            v = ~v
            idx, prev = change[v]
            dp[idx] = prev
            if prev == INF:
                res -= 1

    print(*ans)
resolve()

Solution (Python):

import bisect
import sys

sys.setrecursionlimit(202020)

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

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

DP = [inf]*(N+1)
stack = []
ans = [-1]*N
seen = [False]*N


def dfs(gragh, v): 
    """
    global A
    global DP
    global ans
    global stack 
    global seen
    """
    
    seen[v] = True
    ind = bisect.bisect_left(DP,A[v])
    mae = DP[ind]
    DP[ind] = A[v]
    stack.append([ind,mae])
    
    ans[v] = bisect.bisect_left(DP,inf)
    
    for next_v in gragh[v]:
        if seen[next_v]: 
            continue
        
        dfs(gragh,next_v)
        
    ind,mae = stack.pop()
    DP[ind] = mae
    
    return



dfs(on,0)
for a in ans:
    print(a)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
edges = [[] for _ in range(n)]
dp = [10**10]*n
for _ in range(n-1):
    u,v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

ans = [None]*n
ans[0] = 1
dp[0] = a[0]
def dfs(k, p, dp):
    flag = False
    for v in edges[k]:
        if v != p:
            l = bl(dp, a[v])
            if dp[l] > a[v]:
                idx = l
                tmp = dp[l]
                dp[l] = a[v]
                flag = True
                if tmp == 10**10:
                    ans[v] = ans[k] + 1
                else:
                    ans[v] = ans[k]
            else:
                ans[v] = ans[k]
            dfs(v, k, dp)
            if flag:
                dp[idx] = tmp
                flag = False
    return 
dfs(0, -1, dp)
for i in ans:
    print(i)

Solution (Python):
import sys
import copy
import bisect

sys.setrecursionlimit(202020)

INF = 10**12
MAX_N = 202020

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

dp = [INF for _ in range(MAX_N)]
ans = [0 for _ in range(N)]

def dfs(v, p=-1):
    i = bisect.bisect_left(dp, a[v])
    old = dp[i]
    dp[i] = a[v]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

dp[0] = -INF
dfs(0)
print(*ans)

Solution (Python):
import bisect
import sys
sys.setrecursionlimit(10**6)
INF = 10**10

N = int(input())
A = [0] + list(map(int,input().split()))

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

ans= [0 for i in range(N+1)]
depth = [-1 for n in range(N+1)]
def dfs(s, d, dp): 
    depth[s] = d
    idx = bisect.bisect_left(dp,A[s])
    history = dp[idx] 
    dp[idx] = A[s]
    ans[s] = bisect.bisect_left(dp, INF)
    for i in adj[s]:
        if depth[i]==-1:
            dfs(i, d+1, dp)
    dp[idx] = history 
dp = [INF] * len(A)
dfs(1, 0, dp)
for n in range(1,N+1):
    print(ans[n])

Solution (Python):
from bisect import bisect_left
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

ans = [0 for i in range(n)]
dp = [10**10 for _ in range(n+1)]
check = [True for _ in range(n)]
def dfs(now):
    check[now] = False
    ite = bisect_left(dp, a[now])
    tmp = dp[ite]
    dp[ite] = a[now]
    ans[now] = bisect_left(dp, 10**10)
    
    for to in G[now]:
        if check[to]:
            dfs(to)
    dp[ite] = tmp

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

Solution (Python):
from bisect import bisect_left


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    tree = [list() for _ in range(N)]
    for _ in range(N-1):
        u, v = [int(x) for x in input().split()]
        u -= 1
        v -= 1
        tree[u].append(v)
        tree[v].append(u)

    ans = [1] * N

    
    def dfs(u, par):
        nonlocal ans
        nonlocal dp
        pos = bisect_left(dp, A[u])
        old = dp[pos]
        dp[pos] = A[u]

        ans[u] = bisect_left(dp, float("inf")) - 1

        for v in tree[u]:
            if v == par:
                continue
            dfs(v, u)

        dp[pos] = old

    dp = [float("inf")] * (N+1)
    dp[0] = float("-inf")
    dfs(0, -1)

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


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**6)
    main()

Solution (Python):
from bisect import bisect_left
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

ans = [0 for i in range(n)]
dp = [10**10 for _ in range(n+1)]
check = [True for _ in range(n)]
def dfs(now):
    check[now] = False
    ite = bisect_left(dp, a[now])
    tmp = dp[ite]
    dp[ite] = a[now]
    ans[now] = bisect_left(dp, 10**10)
    
    for to in G[now]:
        if check[to]:
            dfs(to)
    dp[ite] = tmp

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

Solution (Python):
import bisect
import sys
sys.setrecursionlimit(10**6)

N = int(input())
A = [0] + list(map(int,input().split()))

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

ans= [0 for i in range(N+1)]

INF = 10**10

depth = [-1 for n in range(N+1)]
def dfs(s, d, lis): 
    depth[s] = d
    idx = bisect.bisect_left(lis,A[s])
    lis[idx], lis_c = A[s], lis[idx]
    ans[s] = bisect.bisect_left(lis, INF)
    for i in adj[s]:
        if depth[i]==-1:
            dfs(i, d+1, lis)
    lis[idx] = lis_c
lis = [INF] * len(A)
dfs(1, 0, lis)
for n in range(1,N+1):
    print(ans[n])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from itertools import combinations_with_replacement, combinations
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = LI()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

depth = [0] * n
def euler_tour():
    euler = []
    dq = deque([0])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [u]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                dq += [v]
            
            else:
                depth[v] = depth[u] + 1
                dq2 += [v]
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return euler


order = euler_tour()
ans = [1] * n
P = [0] * n
LIS = [A[0]]
pre = 0
ret = 1
for j in range(1, len(order)):
    i = order[j]
    if depth[i] > depth[pre]:
        if A[i] > LIS[-1]:
            LIS += [A[i]]
            ret += 1
            P[i] = (-1, 0)
        else:
            idx = bisect_left(LIS, A[i])
            P[i] = (idx, LIS[idx])
            LIS[idx] = A[i]
        ans[i] = ret
    else:
        idx, e = P[pre]
        if idx == -1:
            LIS.pop()
            ret -= 1
        else:
            LIS[idx] = e
    pre = i

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

Solution (Python):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

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



idle_max=10**18

stack=deque([0])
visited={0}

miti_to_0=[-1 for i in range(N)]
miti=[set() for i in range(N)]

while stack:
    a=stack.popleft()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            miti_to_0[p]=a
            miti[a].add(p)
            stack.append(p)

stack=[0]
visited={0}
dp=[A[0]]
decodelst=[]
dic=defaultdict(int)
dic[0]=1
while stack:
    
    
    a=stack.pop()
    if miti[a]:
        p=miti[a].pop()

        if A[p]>dp[-1]:

            decodelst.append([len(dp),A[p],-1])
            dp.append(A[p])
            dic[p]=len(dp)


        else:
            i=bisect_left(dp,A[p])
            decodelst.append([i,A[p],dp[i]])
            dp[i]=A[p]
            dic[p]=len(dp)
        stack.append(p)
    else:
        if miti_to_0[a]==-1:
            break
        i,p,f=decodelst.pop()
        if f==-1:
            dp.pop()
        else:
            dp[i]=f
        stack.append(miti_to_0[a])
for i in range(N):
    print(dic[i])

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