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):
n = int(input())
a = list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)
    
stack = [1]
dp = [[] for _ in range(n+1)]
dp[1] = [a[0]]
ans = [1]*(n+1)
checked = []
while stack:
    b = stack.pop()
    if b in checked:
        continue
    checked.append(b)
    e = dp[b]
    x = len(e)
    for i in t[b]:
        if i in checked:
            continue
        stack.append(i)
        c = a[i-1]
        if e[-1] < c:
            dp[i] = e.copy()+[c]
            ans[i] = x+1
            d = dp[i][::-1][1:]
        else:
            dp[i] = e.copy()
            ans[i] = x
            d = dp[i][::-1]
        for j,k in enumerate(d):
            if j == x-1 and k > c:
                k = c
            elif j == 0:
                y = k
            elif k > c and y < c:
                k = c
            y = k
                
for i in ans[1:]:
    print(i)

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

INF = float('inf')
dp = [INF]*(n+1)
ans = [1]*(n+1)
checked = [False]*(n+1)
checked[1] = True
changes = []

def search(x):
    ind = bisect.bisect_left(dp,a[x-1])
    changes.append([ind,dp[ind]])
    dp[ind] = a[x-1]
    ans[x] = bisect.bisect_left(dp,INF)
    
    for i in t[x]:
        if not checked[i]:
            checked[i] = True
            search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
for i in a[1:]:
    print(i)

n = int(input())
a = list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)
    
stack = [1]
dp = [[] for _ in range(n+1)]
dp[1] = [a[0]]
ans = [1]*(n+1)
checked = []
while stack:
    b = stack.pop()
    if b in checked:
        continue
    checked.append(b)
    e = dp[b]
    x = len(e)
    for i in t[b]:
        if i in checked:
            continue
        stack.append(i)
        c = a[i-1]
        d = dp[i]
        if e[-1] < c:
            d = e+[c]
            ans[i] = x+1
        else:
            d = e.copy()
            ans[i] = x
        for j in range(x-1,-1,-1):
            if j == 0 and d[j] > c:
                d[j] = c
            elif d[j] > c and d[j-1] < c:
                d[j] = c
                
for i in ans[1:]:
    print(i)

import bisect
import sys
sys.setrecursionlimit(10**7)

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

m = 10**18
dp = [m]*(n+1)
ans = [1]*(n+1)
checked = [False]*(n+1)
checked[1] = True
changes = []

def search(x):
    ind = bisect.bisect_left(dp,a[x])
    changes.append((ind,dp[ind]))
    dp[ind] = a[x]
    ans[x] = bisect.bisect_left(dp,m)
    
    for i in t[x]:
        if not checked[i]:
            checked[i] = True
            search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
for i in ans[1:]:
    print(i)

Verdicts: Wrong Answer

Runtime Error

Runtime Error

Accepted