Problem: 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}.

Submission attempts (in order):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


from bisect import bisect_left, bisect_right, insort_left


class BinarySearchTree:
    def __init__(self, ls: list = []):
        
        self.bst = ls  

    def __repr__(self):
        return f'BST:{self.bst}'

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

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        insort_left(self.bst, x)

    def remove(self, x):
        
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        
        return bisect_right(self.bst, x)

    def find(self, x):
        
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        
        idx_del = self.bisect_left(x) + 1
        if idx_del - 1 == len(self.bst):  
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd


N = read_a_int()
A = read_ints()
Tree = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = read_ints()
    u -= 1
    v -= 1
    Tree[u].append(v)
    Tree[v].append(u)

LIS = BinarySearchTree([-1])

ans = [-1] * N


@njit
def dfs(u, p, LIS):  
    
    LIS.insert_replace_right(A[u])
    ans[u] = len(LIS) - 1
    # print(u, LIS.bst)
    if len(Tree[u]) > 2 or u == 0:  
        for nu in Tree[u]:
            if nu == p:
                continue
            dfs(nu, u, BinarySearchTree(LIS.bst.copy()))  
    elif len(Tree[u]) == 2:  
        for nu in Tree[u]:
            if nu == p:
                continue
            dfs(nu, u, LIS)


# def dfs(u, p, LIS):  
#     
#     LIS.insert_replace_right(A[u])
#     ans[u] = len(LIS) - 1
#     for nu in Tree[u]:
#         if nu == p:
#             continue
#         dfs(nu, u, BinarySearchTree(LIS.bst.copy()))


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




import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x): return int(x) - 1


def read_ints(tozero=False):
    if tozero == False:
        return list(map(int, read().split()))
    else:
        return list(map(mina1, read().split()))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(True)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  


def dfs(now, p):  
    a = A[now]
    
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   
        LIS[idx] = a  

    ans[now] = len(LIS)  
    
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


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


Verdicts: Runtime Error

Accepted