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):
# coding: utf-8
import sys
sysread = sys.stdin.readline
sys.setrecursionlimit(10**7)
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    dp = [float('inf')] * (N+1)
    dp[0] = -float('inf')
    dp2 = [0] * (N+1)
    paths = []
    actions = []# (idx, pre, pro)
    def dfs(node, parent=None):
        a = A[node]
        seen[node] = True
        if parent == None:
            paths.append(node)
            actions.append((1, dp[1], a))
            dp[1] = a
        else:
            while True:
                tmp = paths.pop()
                if tmp == parent:
                    paths.append(tmp)
                    paths.append(node)
                    break
                else:
                    idx, pre, pro = actions.pop()
                    dp[idx] = pre


            idx = bin_search(dp[:len(paths)], a)
            if idx == float('inf'):
                actions.append((len(paths), float('inf'), a))
                dp[len(paths)] = a
            else:
                actions.append((idx, dp[idx], a))
                dp[idx] = a
        print(dp.index(float('inf'))-1)
        for next in to[node]:
            if not seen[next]:
                dfs(next, node)
    dfs(1)

    for i in range(1, N+1):
        print()
    return None

def bin_search(A, x):
    '''
    return index which is lowest in values more than or equal to x
    '''
    low = 0
    high = len(A) - 1
    c = (low + high) // 2
    if A[-1] < x: return float('inf')
    while high - low > 1:
        if A[c] < x:
            low = c
            c = (low + high) // 2

        elif A[c] > x:
            high = c
            c = (high + low) // 2
        else:
            return c
    return high

if __name__ == "__main__":
    run()

# coding: utf-8
import sys
sysread = sys.stdin.readline
sys.setrecursionlimit(10**7)
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    stack = [1]
    tree_score = [-1] * (N+1)
    dp = [[float('inf')] for _ in range(N+1)]
    dp2 = [0] * (N+1)
    def dfs(node, length=0, parent=None):
        seen[node] = True
        stack.append(node)
        length += 1

        if parent == None:
            dp[node].append(A[node])
            dp2[node] = 1
        else:
            dp2[node] = dp2[parent]
            a = A[node]
            done = False
            for i, val in enumerate(dp[parent][1:], 1):
                if val > a and not done:
                    if val == float('inf'):
                        dp2[node] += 1
                    dp[node].append(a)
                    done = True
                else:
                    dp[node].append(val)
            if dp[node][-1] < a:
                dp[node].append(a)
                dp2[node] += 1
            else:
                dp[node].append(float('inf'))

        for next in to[node]:
            if not seen[next]:
                dfs(next, length, node)

    dfs(1)

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


if __name__ == "__main__":
    run()
    from time import time as TTT
    a = [0] * 10**5
    t1 = TTT()
    for _ in range(10**5):
        b = a.copy()
    t2 = TTT()
    print(t2-t1, 'sec')
    for _ in range(10**5):

        c = a[:]
    t3 = TTT()
    print(t3 - t2, 'sec')

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    dp = [float('inf')] * (N+2)
    dp[0] = -float('inf')
    ddp2 = [0]
    paths = []
    actions = []# (idx, pre, pro)
    ans = [0] * (N+1)
    def dfs(node, parent=None):

        a = A[node]
        seen[node] = True
        if parent == None:
            actions.append((1, dp[1], a, 1))
            dp[1] = a
            ddp2[0] += 1
        else:
            idx = bin_search(dp, a)
            if dp[idx] == float('inf'):
                actions.append((idx, dp[idx], a, 1))
                ddp2[0] += 1
            else:
                actions.append((idx, dp[idx], a, 0))
            dp[idx] = a
        ans[node] = ddp2[0]
        for next in to[node]:
            if not seen[next]:
                dfs(next, node)

        idx, pre, pro, change = actions.pop()
        dp[idx] = pre
        ddp2[0] -= change

    dfs(1)
    for s in ans[1:]:
        print(s)
    return None

def bin_search(A, x):
    '''
    return index which is lowest in values more than or equal to x
    '''
    low = 0
    high = len(A) - 1
    c = (low + high) // 2
    if A[-1] < x: return float('inf')
    while high - low > 1:
        if A[c] < x:
            low = c
            c = (low + high) // 2

        elif A[c] > x:
            high = c
            c = (high + low) // 2
        else:
            return c
    return high

if __name__ == "__main__":
    run()

Verdicts: Runtime Error

Time Limit Exceeded

Accepted