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
sys.setrecursionlimit(10**7)
from bisect import bisect_left as bl
def main(n,a):
  ans=[0]*n
  ki=[[] for _ in range(n)]
  for _ in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append(v)
    ki[v].append(u)
  inf=float('inf')
  p={}
  dp=[inf]*(n+1)
  dp[0]=0
  
  maxa=max(a)+1

  def dfs(v,p,dp):
    x=a[v]
    idx=bl(dp,x)
    tmp=dp[idx]
    dp[idx]=x
    
    ans[v]=bl(dp,maxa)-1
    for nv in ki[v]:
      if nv==p:continue
      dfs(nv,v,dp)
    dp[idx]=tmp
  dfs(0,-1,dp)
  print(*ans,sep='\n')

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

Solution (Python):
from bisect import bisect_left

N=int(input())
*A,=map(int,input().split())
INF=10**20
G=[[] for _ in range(N)]
ab = [tuple(map(int,input().split())) for _ in range(N-1)]
for a,b in ab:
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(a0):
    seen =[0]*len(G)
    todo = [~a0, a0]
    while todo:
        a = todo.pop()
        if a >= 0:
            seen[a] = 1
            idx = bisect_left(lis,A[a])
            his[a] = (idx,lis[idx])
            lis[idx] = A[a]
            dp[a] = bisect_left(lis,INF)
            for b in G[a]:
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          idx,val = his[~a]
          lis[idx] = val
    return
  
lis = [INF]*N
dp = [0]*N
his = {}
dfs(0)
print(*dp,sep="\n")

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

def dfs(v):
 
 pos=bisect.bisect_left(dp,arr[v]) 
 changes.append((pos,dp[pos])) 
 dp[pos]=arr[v]
 ans[v]=bisect.bisect_left(dp,10**18) 
 for u in g[v]:
   if checked[u]==0:
     checked[u]=1
     dfs(u)
 
 pos,val=changes.pop() 
 dp[pos]=val

n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dp=[10**18 for _ in range(n+1)] 
changes=[]
dfs(1)
for i in range(1,n+1):
 print(ans[i])

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

def dfs(v):
 
 pos=bisect.bisect_left(dp,arr[v]) 
 changes.append((pos,dp[pos])) 
 dp[pos]=arr[v]
 ans[v]=bisect.bisect_left(dp,10**18) 
 for u in g[v]:
   if checked[u]==0:
     checked[u]=1
     dfs(u)
 
 pos,val=changes.pop() 
 dp[pos]=val

n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dp=[10**18 for _ in range(n+1)] 
changes=[]
dfs(1)
for i in range(1,n+1):
 print(ans[i])

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

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

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

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

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

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

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

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

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

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


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

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

dfs(0)
for i in range(N):
	print(lisl[i])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

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

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

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







N = getN()
A = getList()
query = [getList() for i in range(N - 1)]

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

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


def dfs(u):
    global lis
    for i in dist[u]:
        if ignore[i] != 1:
            ignore[i] = 1
            
            plus = 0 
            change = (0, 0, 0) 

            if A[i] > lis[-1]:
                lis.append(A[i])
                plus = 1
            else:
                index = bisect_left(lis, A[i])
                change = (1, index, lis[index])
                lis[index] = A[i]
            rec[i] = len(lis)
            dfs(i)
            
            if plus:
                lis.pop()
            else:
                lis[change[1]] = change[2]

dfs(0)
for i in rec:
    print(i)

Solution (Python):
import bisect
import sys
sys.setrecursionlimit(1<<30)
def dfs(i,LIS):
    if a[i] > LIS[-1]:
        LIS.append(a[i])
        ans[i] = len(LIS)
        for j in edges[i]:
            if parent[i] != j:
                parent[j] = i
                dfs(j,LIS)
        LIS.pop()
    else:
        index = bisect.bisect_left(LIS, a[i])
        x = LIS[index]
        LIS[index] = a[i]
        ans[i] = len(LIS)
        for j in edges[i]:
            if parent[i] != j:
                parent[j] = i
                dfs(j,LIS)
        LIS[index] = x

N = int(input())
a = [0]+list(map(int,input().split()))
edges = [[] for _  in range(N+1)]
ans = [-1]*(N+1)
parent = [-1]*(N+1)
for i in range(N-1):
    u,v = map(int,input().split())
    edges[u].append(v)
    edges[v].append(u)
LIS = [a[1]]
dfs(1,LIS)
for i in ans[1:]:
    print(i)

Solution (Python):

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
import sys
sys.setrecursionlimit(10**6)
n = ni()
A = lma()
tree = [[] for i in range(n)]
INF = 10**10
for i in range(n-1):
    u,v = ma();u-=1;v-=1
    tree[u].append(v)
    tree[v].append(u)

def isok(num,val):
    return num<val
def bisect(ls,val): 
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok 
def LIS_1(x,ls,right):
    idx = bisect(ls,x)+1
    if idx+1>right:
        ret= idx+1
    else:
        ret=right
    rewind_idxval.append((idx,ls[idx]))
    ls[idx]=x
    
    return ret
def DFS_LIS(prev,ls,right):
    ans[prev]= LIS_1(A[prev],ls,right)
    for node in tree[prev]:
        if not visited[node]:
            visited[node]=True
            DFS_LIS(node,ls,ans[prev])
    
    idx,pval = rewind_idxval.pop()
    ls[idx] = pval

ans = [0]*n
s = 0
right=0
rewind_idxval=collections.deque()
visited=[False]*n
visited[s]=True
ls=[INF]*n
DFS_LIS(s,ls,right)

for a in ans :
    print(a)

Solution (Python):
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

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

graph = [[] for _ in range(n+1)]

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

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
A = IL()
graph = [[] for i in range(N)]
for _ in range(N-1):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  
def dfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  LIS = [INF] * N
  LISmemo = [None] * N
  ans = [None] * N
  q = deque([start])
  while q:
    u = q.pop()
    if u >= 0:
      p = bisect.bisect_left(LIS,A[u])
      LISmemo[u] = (p,LIS[p])
      LIS[p] = A[u]
      ans[u] = bisect.bisect_left(LIS,INF)
      q.append(~u)
      for v in graph[u]:
        if d[v] != INF: continue
        d[v] = d[u] + 1
        q.append(v)
    else:
      if u == ~0: continue
      p,a = LISmemo[~u]
      LIS[p] = a
      
  return ans

ans = dfs(graph,0)

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from bisect import bisect_left
def main(N,a,tr):
  ans=[0]*N
  dp=[float('inf')]*(N+1)
  dp[0]=0
  maxa=max(a)+1
  def dfs(p,v,dp):
    i=bisect_left(dp,a[v])
    tmp=dp[i]
    dp[i]=a[v]
    ans[v]=bisect_left(dp,maxa)-1
    for nv in tr[v]:
      if nv!=p:
        dfs(v,nv,dp)
    dp[i]=tmp
  dfs(-1,0,dp)
  print(*ans,sep='\n')
if __name__=='__main__':
  N=int(input())
  a=list(map(int,input().split()))
  tr=[[] for _ in range(N)]
  for _ in range(N-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    tr[u].append(v)
    tr[v].append(u)
  main(N,a,tr)

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

def solve(N, A, UV):
    G = [[0] * 0 for _ in range(N)]
    for i in range(N-1):
        u, v = UV[i]
        G[u].append(v)
        G[v].append(u)
    L = [A[0]]
    Ans = np.zeros(N, dtype=np.int64)
    stack = np.zeros((202020, 5), dtype=np.int64)  
    idx_stack = 0
    while idx_stack >= 0:
        v, state, idx_Gv, idx_L, old = stack[idx_stack]
        idx_stack -= 1
        if state == 0:
            Ans[v] = len(L)
        if state == 2:
            if idx_L == -1:
                del L[-1]
            else:
                L[idx_L] = old
        Gv = G[v]
        if len(Gv) == idx_Gv:
            continue
        u = Gv[idx_Gv]
        G[u].remove(v)
        Au = A[u]
        if Au > L[-1]:
            L.append(Au)
            idx_stack += 1
            stack[idx_stack] = (v, 2, idx_Gv + 1, -1, -1)
            idx_stack += 1
            stack[idx_stack] = (u, 0, 0, -1, -1)
            continue
        else:
            idx_L = np.searchsorted(L, Au)
            old = L[idx_L]
            L[idx_L] = Au
            idx_stack += 1
            stack[idx_stack] = (v, 2, idx_Gv + 1, idx_L, old)
            idx_stack += 1
            stack[idx_stack] = (u, 0, 0, -1, -1)
            continue
    return Ans

numba_compile([
    [solve, "i8[:](i8,i8[:],i8[:,:])"]
])

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    A = np.array(input().split(), dtype=np.int64)
    UV = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(N-1, 2) - 1
    Ans = solve(N, A, UV)
    print("\n".join(map(str, Ans.tolist())))

main()

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

def solve(N, A, UV):
    G = [[0] * 0 for _ in range(N)]
    for i in range(N-1):
        u, v = UV[i]
        G[u].append(v)
        G[v].append(u)
    L = [A[0]]
    Ans = np.zeros(N, dtype=np.int64)
    stack = [(0, 0, 0, -1, -1)]  
    while stack:
        v, state, idx_Gv, idx_L, old = stack.pop()
        if state == 0:
            Ans[v] = len(L)
        if state == 2:
            if idx_L == -1:
                del L[-1]
            else:
                L[idx_L] = old
        Gv = G[v]
        if len(Gv) == idx_Gv:
            continue
        u = Gv[idx_Gv]
        G[u].remove(v)
        Au = A[u]
        if Au > L[-1]:
            L.append(Au)
            stack.append((v, 2, idx_Gv + 1, -1, -1))
            stack.append((u, 0, 0, -1, -1))
            continue
        else:
            idx_L = np.searchsorted(L, Au)
            old = L[idx_L]
            L[idx_L] = Au
            stack.append((v, 2, idx_Gv + 1, idx_L, old))
            stack.append((u, 0, 0, -1, -1))
            continue
    return Ans

numba_compile([
    [solve, "i8[:](i8,i8[:],i8[:,:])"]
])

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    A = np.array(input().split(), dtype=np.int64)
    UV = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(N-1, 2) - 1
    Ans = solve(N, A, UV)
    print("\n".join(map(str, Ans.tolist())))

main()

Solution (Python):
import sys
from bisect import bisect_left
def main():
    sys.setrecursionlimit(202020)
    N = int(input())
    A = [0] + list(map(int, input().split()))
    G = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        G[u].append(v)
        G[v].append(u)
    L = [A[1]]
    Ans = [0] * (N+1)
    def dfs(v):
        Ans[v] = len(L)
        for u in G[v]:
            G[u].remove(v)
            Au = A[u]
            if Au > L[-1]:
                L.append(Au)
                dfs(u)
                del L[-1]
            else:
                idx = bisect_left(L, Au)
                old = L[idx]
                L[idx] = Au
                dfs(u)
                L[idx] = old
    dfs(1)
    print("\n".join(map(str, Ans[1:])))

main()

Solution (Python):

import math
import bisect

n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = map(int,input().split())
    if u > v:
        u, v = v, u
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])
    tree[uv[1]].append(uv[0])
    

queue = [1]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        for child in tree[cur]:
            if used[child] == 0:
                queue.append(child)
    else:
        queue.pop()

        
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1
for i in range(n):
    print(ans[i+1])

Solution (Python):
from bisect import bisect_left
from collections import deque
import sys

sys.setrecursionlimit(200001)

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)

INF = 10**11
ans = [0]*N
dp = []
stack = deque([])

def LISonTree(num,pre):
    
    
    p = bisect_left(dp,a[num])

    
    
    

    if p >= len(dp):
        stack.appendleft((len(dp),INF))
        dp.append(a[num])
    else:
        stack.appendleft((p,dp[p]))
        dp[p] = a[num]
        
    
    q = bisect_left(dp,INF)
    ans[num] = q

    
    
    
    

    for x in graph[num]:
        if x == pre:
            continue
        LISonTree(x,num)
    
    changed_p, changed_v = stack.popleft()

    dp[changed_p] = changed_v

    
    
    

LISonTree(0,-1)


for y in ans:
    print(y)

Solution (Python):
import bisect
I = [int(_) for _ in open(0).read().split()]
N = I[0]
A = [0] + I[1:1 + N]
U = [0] + I[1 + N::2]
V = [1] + I[2 + N::2]
G = [set() for _ in range(N + 1)]
for u, v in zip(U, V):
    G[u].add(v)
    G[v].add(u)
ans = [10**10] * (N + 1)
stack = [(0, 1, 1, A[1], 0)]
dp = [-10 ** 10] + [10 ** 10] * N
while stack:
    i, j, p, q, d = stack.pop()
    if d:
        dp[p] = q
        continue
    stack += [(j, i, p, dp[p], 1)]
    dp[p] = q
    ans[j] = bisect.bisect_left(dp, 10 ** 10) - 1
    while G[j]:
        k = G[j].pop()
        if i == k:
            continue
        q = A[k]
        p = bisect.bisect_left(dp, q)
        stack += [(j, k, p, q, 0)]
print(*ans[1:], sep='\n')

Solution (Python):
import sys
import numpy as np

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

def to_undirected(G):
    N = len(G)
    G = np.vstack((G, G))
    G[N:, 0] = G[:N, 1]
    G[N:, 1] = G[:N, 0]
    ind = G[:, 0].argsort()
    return G[ind]

def euler_tour(N, G, ind, root):
    parent = np.zeros(1 + N, np.int64)
    tour = np.zeros(N + N, np.int64)
    st = np.empty(len(G) + 10, np.int64)
    p = 0

    def add(v):
        nonlocal p
        st[p] = v
        p += 1

    def pop():
        nonlocal p
        p -= 1
        return st[p]

    add(-root)
    add(root)
    n = 0
    while p:
        v = pop()
        tour[n] = v
        n += 1
        if v > 0:
            for i in range(ind[v - 1], ind[v]):
                w = G[i, 1]
                if w == parent[v]:
                    continue
                add(-w)
                add(w)
                parent[w] = v
    return tour, parent

def main(N, A, G):
    G = to_undirected(G)
    ind = np.searchsorted(G[:, 0], np.arange(N + 1), 'right')
    tour, parent = euler_tour(N, G, ind, 1)
    INF = 1 << 60
    reverse = np.empty((N + 1, 2), np.int64)
    dp = np.full(N + 1, INF, np.int64)
    ans = np.empty(N + 1, np.int64)
    for v in tour:
        if v > 0:
            i = np.searchsorted(dp, A[v])
            reverse[v] = i, dp[i]
            dp[i] = A[v]
            ans[v] = np.searchsorted(dp, INF)
        else:
            v = -v
            i, x = reverse[v]
            dp[i] = x
    return ans[1:]

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i4 = numba.int32
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    to_undirected = cc_export(to_undirected, (i8[:, :], ))
    euler_tour = cc_export(euler_tour, (i8, i8[:, :], i8[:], i8)) 
    main = cc_export(main, (i8, i8[:], i8[:, :]))
    cc.compile()

from my_module import main

N = int(readline())
A = np.array([0] + readline().split(), np.int64)
G = np.array(read().split(), np.int64).reshape(-1, 2)

ans = main(N, A, G)
print('\n'.join(map(str, ans.tolist())))

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8
from numba.types import Omitted

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

@njit((i8[:, :], ), cache=True)
def to_undirected(G):
    N = len(G)
    G = np.vstack((G, G))
    G[N:, 0] = G[:N, 1]
    G[N:, 1] = G[:N, 0]
    ind = G[:, 0].argsort()
    return G[ind]

@njit([(i8, i8[:, :], i8[:], i8), (i8, i8[:, :], i8[:], Omitted(1))],
      cache=True)
def euler_tour(N, G, ind, root=1):
    parent = np.zeros(1 + N, np.int64)
    tour = np.zeros(N + N, np.int64)
    st = np.empty(len(G) + 10, np.int64)
    p = 0

    def add(v):
        nonlocal p
        st[p] = v
        p += 1

    def pop():
        nonlocal p
        p -= 1
        return st[p]

    add(-root)
    add(root)
    n = 0
    while p:
        v = pop()
        tour[n] = v
        n += 1
        if v > 0:
            for i in range(ind[v - 1], ind[v]):
                w = G[i, 1]
                if w == parent[v]:
                    continue
                add(-w)
                add(w)
                parent[w] = v
    return tour, parent

@njit((i8, i8[:], i8[:, :]), cache=True)
def main(N, A, G):
    G = to_undirected(G)
    ind = np.searchsorted(G[:, 0], np.arange(N + 1), 'right')
    tour, parent = euler_tour(N, G, ind)
    INF = 1 << 60
    reverse = np.empty((N + 1, 2), np.int64)
    dp = np.full(N + 1, INF, np.int64)
    ans = np.empty(N + 1, np.int64)
    for v in tour:
        if v > 0:
            i = np.searchsorted(dp, A[v])
            reverse[v] = i, dp[i]
            dp[i] = A[v]
            ans[v] = np.searchsorted(dp, INF)
        else:
            v = -v
            i, x = reverse[v]
            dp[i] = x
    return ans[1:]

N = int(readline())
A = np.array([0] + readline().split(), np.int64)
G = np.array(read().split(), np.int64).reshape(-1, 2)

ans = main(N, A, G)
print('\n'.join(map(str, ans.tolist())))

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect


N = int(input())
a = [0] + list(map(int, input().split()))
al = [[] for i in range(N+1)]

for i in range(N-1):
    c, d = list(map(int, input().split()))
    al[c].append(d)
    al[d].append(c)

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

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

def dfs_rec(u):
    x = a[u]
    if x > LIS[-1]:
        pre_idx = len(LIS)
        pre_v = INF
        LIS.append(x)
    else:
        pre_idx = bisect.bisect_left(LIS, x)
        pre_v = LIS[pre_idx]
        LIS[bisect.bisect_left(LIS, x)] = x

    ans[u] = len(LIS)

    visited[u] = 1
    for v in al[u]:
        if visited[v] == 0:
            dfs_rec(v)

    if pre_v == INF:
        LIS.pop()
    else:
        LIS[pre_idx] = pre_v

dfs_rec(1)

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

Solution (Python):
from bisect import bisect_left as bl
import sys
sys.setrecursionlimit(10**6)
n=int(input())
a=list(map(int,input().split()))
t=[[]for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    t[u-1].append(v-1)
    t[v-1].append(u-1)
b=[0]*n
dp=[float("inf")]*n
def f(c,d):
    h=bl(dp,a[c])
    g=dp[h]
    dp[h]=min(dp[h],a[c])
    b[c]=bl(dp,float("INF"))
    for i in t[c]:
        if i!=d:f(i,c)
    dp[h]=g
f(0,-1)
for i in b:
    print(i)

Solution (Python):


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

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

for i in range(N-1):
  a,b = map(int, input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)

INF = 10**9+1


q = [0]    
dp = [INF]*N  
ans = [0]*N   
lis_len = 0   
idx = [-1]*N  
old = [-1]*N  
prev = [-1]*N 

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

    for nxt in G[now]:
      if nxt == prev[now]:
        continue
      prev[nxt] = now
      
      
      q.append((-1)*nxt)
      q.append(nxt)
  
  else:
    
    now = (-1)*now
    dp[idx[now]] = old[now]
    x = dp[idx[now]] 
    if x == INF:
      lis_len -= 1
    

for a in ans:
  print(a)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
UV=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
for i,j in UV:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
v=[0]*N
d=[10**9+1]*N
stk=[]
ans=[0]*N
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**9)
def dfs(p,l):
    i=bisect_left(d,A[p])
    stk.append((i,d[i]))
    d[i]=A[p]
    if i==l:
        l+=1
    ans[p]=l
    for n in c[p]:
        if v[n]==0:
            v[n]=1
            dfs(n,l)
    i,x=stk.pop()
    d[i]=x
v[0]=1
dfs(0,0)
print(*ans,sep='\n')