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
input = sys.stdin.readline
from collections import deque
import bisect

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

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

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

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

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

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])
            if len(dp) <= i:
                dp.append(A[v])
                ans[v] = len(dp)
                dfs(v, u, dp)
                dp.pop()
            else:
                b = dp[i]
                dp[i] = A[v]
                ans[v] = len(dp)
                dfs(v, u, dp)
                dp[i] = b
    dp = [A[1]]
    dfs(1, 0, dp)

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

    


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):
def main():
    from bisect import bisect_left
    import sys
    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    inf = 1 << 30

    N = int(input())
    *a, = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    ans = [0] * N
    lis = [inf] * N

    def dfs(v, p=-1):
        i = bisect_left(lis, a[v])
        prev_at_i = lis[i]
        lis[i] = a[v]
        ans[v] = bisect_left(lis, inf)
        for u in g[v]:
            if p == u: continue
            dfs(u, v)
        lis[i] = prev_at_i

    dfs(0)

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


if __name__ == '__main__':
    main()

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

    inf = 1 << 30

    N = int(input())
    *a, = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    ans = [0] * N
    lis = [inf] * N
    lis[0] = a[0]

    def dfs(v, p=-1):
        ans[v] = bisect_left(lis, inf)
        for u in g[v]:
            if p == u: continue
            i = bisect_left(lis, a[u])
            prev_at_i = lis[i]
            lis[i] = a[u]
            dfs(u, v)
            lis[i] = prev_at_i

    dfs(0)

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


if __name__ == '__main__':
    main()

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

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

inf = 10 ** 10
d = [inf for _ in range(n)]
dp = [inf for _ in range(n)]

def dfs(cur, prev):
    memo = bisect.bisect_left(dp, a[cur])
    memo_v = dp[memo]
    dp[memo] = a[cur]
    d[cur] = bisect.bisect_left(dp, inf)

    for to in edges[cur]:
        if to != prev:
            dfs(to, cur)

    dp[memo] = memo_v

dfs(0, -1)
for i in range(n):
    print(d[i])

Solution (Python):
import sys
import bisect
sys.setrecursionlimit(10**9)
INF = 2**30
N = int(input())
A = list(map(int, input().split()))
E = []
for i in range(N):
    E.append([])
for i in range(N-1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    E[u].append(v)
    E[v].append(u)

ans = [0] * N
dp = [INF] * N

def dfs(now, par, len):
    ok = bisect.bisect_left(dp, A[now])
    memo = dp[ok]
    dp[ok] = A[now]

    ok1 = bisect.bisect_left(dp, INF)
    ans[now] = ok1

    for to in E[now]:
        if to == par:
            continue
        dfs(to, now, len+1)
    dp[ok] = memo

dfs(0, -1, 0)

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

Solution (Python):
import sys
from copy import copy
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
INF = float('inf')

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 = [INF] * n
dp[0] = a[0]



def dfs(v, v_p):
    ans[v] = bisect_left(dp, INF)

    for v_next in graph[v]:
        if v_next == v_p:
            continue

        idx = bisect_left(dp, a[v_next])
        past = dp[idx]
        dp[idx] = a[v_next]
        dfs(v_next, v)
        dp[idx] = past


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

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

def main():
    n=int(input())
    A=list(map(int, input().split()))
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1; v-=1
        Edges[u].append(v)
        Edges[v].append(u)
    LIS=[10**11]*n
    Ans=[0]*n

    def dfs(v,par):
        idx=bisect_left(LIS,A[v])
        tmp=LIS[idx]
        LIS[idx]=A[v]
        Ans[v]=bisect_left(LIS,10**10)
        for chi in Edges[v]:
            if chi==par:
                continue
            dfs(chi,v)
        LIS[idx]=tmp

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

if __name__=='__main__':
    main()

Solution (Python):
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

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

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
d = dict()
AA = [0]*(N+1)
a2f = [0]*(N+1)
rj = 0
for j, (i, a) in enumerate(iA):
    AA[i] = j
    if a not in d:
        rj = j
    a2f[i] = rj
    d[a] = 1


R = [0]*(N+1)
R[1] = 1
ss = SegTree([0]*(N+1), N+1, -1, max)
stack = [1]
visited = set([1])
path = []
while stack:
    v = stack.pop()
    if v > 0:
        path.append(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)

        R[v] = ss.query(0, N+1)
        for u in G[v]:
            if u in visited:
                continue
            visited.add(u)
            stack += [-v, u]
    else:
        c = path.pop()
        ss.update(AA[c], 0)
for i in range(1, N+1):
    print(R[i])

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


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

edges = [[] for _ in range(n+1)]
for _ in range(n-1):
    from_, to = map(int, input().split())
    edges[from_].append(to)
    edges[to].append(from_)


DP = [10**9+7] * (n+1)
limit = 10**9 + 1
DP[0] = 0
olds = [None] * (n+1)
ans = [0] * n

todo = [1]
while todo:
    node = todo.pop()
    if node > 0:
        num = A[node-1]
        update_idx = bisect.bisect_left(DP, num)
        old = DP[update_idx]
        olds[node] = (old, update_idx)
        DP[update_idx] = num
        lis = bisect.bisect_left(DP, limit) - 1
        ans[node-1] = lis

        todo.append(-node)
        for to in edges[node]:
            if ans[to-1]:
                continue
            todo.append(to)

    else:
        node = -node
        old, update_idx = olds[node]
        DP[update_idx] = old

for res in ans:
    print(res)

Solution (Python):
import bisect


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

edges = [[] for _ in range(n+1)]
for _ in range(n-1):
    from_, to = map(int, input().split())
    edges[from_].append(to)
    edges[to].append(from_)


DP = [10**9+7] * (n+1)
limit = 10**9 + 1
DP[0] = 0
olds = [None] * (n+1)
ans = [0] * n

todo = [1]
while todo:
    node = todo.pop()
    if node > 0:
        num = A[node-1]
        update_idx = bisect.bisect_left(DP, num)
        old = DP[update_idx]
        olds[node] = (old, update_idx)
        DP[update_idx] = num
        lis = bisect.bisect_left(DP, limit) - 1
        ans[node-1] = lis

        todo.append(-node)
        for to in edges[node]:
            if ans[to-1]:
                continue
            todo.append(to)

    else:
        node = -node
        old, update_idx = olds[node]
        DP[update_idx] = old

for res in ans:
    print(res)

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

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

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

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect(dp, 10**18) - 1
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0)
flag = False
for i in range(n):
    print(ansl[i])

Solution (Python):
import bisect,sys

input=sys.stdin.readline
sys.setrecursionlimit(1000000)

N=int(input())
a=list(map(int,input().split()))
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)

dp=[10**20 for i in range(N)]
ans=[-1 for i in range(0,N)]
def dfs(v,pv):
    pos=bisect.bisect_left(dp,a[v])
    prev=dp[pos]
    dp[pos]=a[v]
    ans[v]=bisect.bisect_left(dp,10**18)
    for i in edge[v]:
        if i==pv:
            continue

        dfs(i,v)

    dp[pos]=prev

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

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]
stack = []
n_stack = []
def dfs(node, par, n):
  global ans
  global dp
  global stack
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    stack.append([idx, dp[idx]])
    n_stack.append(n)
    dp[idx] = num
    n = max(n, idx + 1)
    ans[child] = n
    dfs(child, node, n)
    
    idx, num = stack.pop()
    dp[idx] = num
    n = n_stack.pop()

dfs(0, -1, 1)
print(*ans, 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]
stack = []
def dfs(node, par, n):
  global ans
  global dp
  global stack
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    stack.append([idx, dp[idx]])
    dp[idx] = num
    ans[child] = max(n, idx+1)
    
    dfs(child, node, max(n, idx+1))
    
    idx, num = stack.pop()
    dp[idx] = num

dfs(0, -1, 1)
print(*ans, 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]
stack = []
def dfs(node, par):
  global ans
  global dp
  global stack
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    stack.append([idx, dp[idx]])
    dp[idx] = num
    ans[child] = bisect.bisect_left(dp, INF)
    dfs(child, node)
    
    idx, num = stack.pop()
    dp[idx] = num

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

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

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)

lis = [float('inf')] * n
ans = [0] * n

def dp(v, prev):
    i = bisect_left(lis, a[v])
    tmp = lis[i]
    lis[i] = a[v]
    ans[v] = bisect_left(lis, float('inf'))
    for u in G[v]:
        if u != prev:
            dp(u, v)
    lis[i] = tmp

dp(0, -1)
for l in ans:
    print(l)

Solution (Python):
from collections import deque
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline


def euler_tour(tree: list, root: int):
    """根をrootとしたときの辺に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    trail = []
    par = {root: -1}
    stack = [root]
 
    while stack:
        v = stack.pop()
        if v >= 0:  
            trail.append(v)
            stack.append(~v)
            for nxt_v in tree[v]:
                if nxt_v not in par:
                    par[nxt_v] = v
                    stack.append(nxt_v)
 
        else:  
            if ~v == root:
                continue
            trail.append(-par[~v])
 
    return trail


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

tree = [[] for i in range(n)]
for u, v in info:
    u -= 1
    v -= 1
    tree[u].append(v)
    tree[v].append(u)

res = euler_tour(tree, 0)
array_ind = [0]
lis_array = [a[0]]
ans = [0] * n
ans[0] = 1



stack1 = []
stack2 = []
for ind in res[1:]:
    if ind > 0:
        val = a[ind]
        array_ind.append(ind)
        if val > lis_array[-1]:
            lis_array.append(val)
            stack1.append(-1)
            stack2.append(-1)
        else:
            pos = bisect_left(lis_array, val)
            stack1.append(pos)
            stack2.append(lis_array[pos])
            lis_array[pos] = val
        ans[ind] = len(lis_array)
    else:
        del array_ind[-1]
        pos = stack1.pop()
        val = stack2.pop()
        if pos == -1:
            del lis_array[-1]
        else:
            lis_array[pos] = val

for i in range(n):
    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
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
import bisect
INF = 10**10

n = int(input())
a = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for _ 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
lis = [INF] * n
def dfs(p, v):
    place = bisect.bisect_left(lis, a[v])
    val = lis[place]
    lis[place] = a[v]
    ans[v] = bisect.bisect_left(lis, INF)
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(v, nv)
    lis[place] = val

dfs(-1, 0)
for item in ans:
    print(item)

Solution (Python):
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

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

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
d = dict()
AA = [0]*(N+1)
a2f = [0]*(N+1)
rj = 0
for j, (i, a) in enumerate(iA):
    AA[i] = j
    if a not in d:
        rj = j
    a2f[i] = rj
    d[a] = 1


R = [0]*(N+1)
R[1] = 1
ss = SegTree([0]*(N+1), N+1, -1, max)
ss.update(AA[1], 1)
stack = []
for u in G[1]:
    stack += [-1, u]
visited = set([1])
path = [1]
while stack:
    v = stack.pop()
    if v > 0:
        visited.add(v)
        path.append(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)
        R[v] = ss.query(0, N+1)
        for u in G[v]:
            if u in visited:
                continue
            stack += [-v, u]
    else:
        c = path.pop()
        ss.update(AA[c], 0)
for i in range(1, N+1):
    print(R[i])

Solution (Python):
from bisect import bisect_left


def solve(n, a_list, uv_list):
    res = [0] * n
    tree = [[] for _ in range(n)]
    for u, v in uv_list:
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)

    
    visited = [0] * n
    parent = [-1] * n
    tour = [0]
    p = 0
    while True:
        visited[p] = 1
        r = parent[p]
        while len(tree[p]):
            q = tree[p].pop()
            if visited[q] == 0:
                parent[q] = p
                r = q
                break
        if r == -1:
            break
        p = r
        tour.append(p)
    
    

    
    dp = [10 ** 9 + i for i in range(n + 1)]
    dp[0] = 0
    re_visited = [0] * n
    callbacks = []
    for p in tour:
        if re_visited[p] == 0:
            re_visited[p] = 1
            ind = bisect_left(dp, a_list[p])
            callbacks.append((ind, dp[ind]))
            dp[ind] = a_list[p]
            res[p] = bisect_left(dp, 10 ** 9) - 1
        else:
            ind, v = callbacks.pop()
            dp[ind] = v
        
    
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    uv_list = [list(map(int, input().split())) for _ in range(n - 1)]
    res = solve(n, a_list, uv_list)
    for r in res:
        print(r)


def test():
    assert solve(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]]
                 ) == [1, 2, 3, 3, 4, 4, 5, 2, 2, 3]
    assert solve(10, [5, 2, 5, 3, 4, 6, 7, 3, 2, 4],
                 [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 10]]
                 ) == [1, 1, 1, 1, 1, 2, 2, 1, 1, 1]
    assert solve(10, [5, 2, 5, 3, 4, 6, 7, 3, 2, 4],
                 [[1, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10]]
                 ) == [1, 1, 2, 2, 2, 2, 2, 2, 1, 2]
    assert solve(10, [3, 5, 5, 3, 4, 6, 7, 3, 2, 4],
                 [[1, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10]]
                 ) == [1, 2, 2, 2, 2, 3, 3, 2, 2, 2]
    assert solve(10, [3, 3, 3, 3, 3, 3, 3, 3, 3, 3],
                 [[1, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10]]
                 ) == [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]


if __name__ == "__main__":
    test()
    main()

Solution (Python):

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


from collections import defaultdict
import bisect
INF = float("inf")


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


class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def Euler_tour(G, node, visit, DP, prev, ans, A):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			
			x = bisect.bisect_left(DP, A[i])
			prev.append([x, DP[x]])
			DP[x] = A[i]
			ans[i] = bisect.bisect_left(DP, INF)
			
			
			Euler_tour(G, i, visit, DP, prev, ans, A)

	
	x, val = prev.pop()
	DP[x] = val


def main():
	N = int(input())
	A = getlist()
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	
	DP = [INF] * N
	DP[0] = A[0]
	prev = [[0, A[0]]]
	ans = [None] * N
	ans[0] = 1
	visit = ["No"] * N
	visit[0] = "Yes"
	Euler_tour(G, 0, visit, DP, prev, ans, A)
	for i in range(N):
		print(ans[i])


if __name__ == '__main__':
	main()

Solution (Python):
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

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

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
d = dict()
AA = [0]*(N+1)
a2f = [0]*(N+1)
rj = 0
for j, (i, a) in enumerate(iA):
    AA[i] = j
    if a not in d:
        rj = j
    a2f[i] = rj
    d[a] = 1


R = [0]*(N+1)
R[1] = 1
ss = SegTree([0]*(N+1), N+1, -1, max)
ss.update(AA[1], 1)
stack = []
for u in G[1]:
    stack += [-1, u]
visited = set([1])
path = [1]
while stack:
    v = stack.pop()
    if v > 0:
        visited.add(v)
        path.append(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)
        R[v] = ss.query(0, N+1)
        for u in G[v]:
            if u in visited:
                continue
            stack += [-v, u]
    else:
        child = path.pop()
        ss.update(AA[child], 0)
for i in range(1, N+1):
    print(R[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
input = sys.stdin.readline
sys.setrecursionlimit(2*10**5+100)
from bisect import *

def dfs(v, pv):
    j = bisect_left(dp, a[v])
    prev = dp[j]
    dp[j] = a[v]
    ans[v] = bisect_left(dp, 10**18)-1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        dfs(nv, v)
    
    dp[j] = prev

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 = [10**18]*(N+1)
dp[0] = -10**18
ans = [-1]*N
dfs(0, -1)

for ans_i in ans:
    print(ans_i)

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

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())
    g[u-1].append(v-1)
    g[v-1].append(u-1)

lis = [float('inf')]*n
ans = [0]*n

def dfs(now, pre):
    idx = bisect_left(lis, a[now])
    tmp = lis[idx]
    lis[idx] = a[now]
    ans[now] = bisect_left(lis, float('inf'))
    for to in g[now]:
        if to == pre:
            continue
        dfs(to, now)
    lis[idx] = tmp

dfs(0,-1)
for x in ans:
    print(x)

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

INF = float('inf')

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

dp = [-INF]
anss = [0] * N
def dfs(vNow, vPar):
    A = As[vNow]
    if dp[-1] < A:
        dp.append(A)
        tp = 0
    else:
        i = bisect_left(dp, A)
        tp = 1
        iOld, AOld, = i, dp[i]
        dp[i] = A
    anss[vNow] = len(dp)-1

    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        dfs(v2, vNow)

    if tp == 0:
        dp.pop()
    else:
        dp[iOld] = AOld

dfs(0, -1)

print('\n'.join(map(str, anss)))

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

n = int(input())
a = list(map(int, input().split()))
to=[list() 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)

INF=1001001001
dp = [INF]*n
dp[0]=a[0]
ansls=[0]*n
ansls[0]=1
history=deque()
def dfs(u,p,rank):
    for v in to[u]:
        if v==p:
            continue
        idx=bisect.bisect_left(dp,a[v])
        prv=dp[idx]
        dp[idx]=a[v]       
        history.append((idx,prv))
        ansls[v]=bisect.bisect_left(dp,INF)
        dfs(v,u,rank+1)
        while len(history)>rank:
            idx,prv =history.pop()
            dp[idx] = prv

dfs(0,-1,0)

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