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.



Sample input:
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
2
3
3
4
4
5
2
2
3

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


def dfs(now):
    checked[now] = 1
    sequences[now] += [As[now]]
    ans[now] = LIS(sequences[now])
    for i in tree[now]:
        if checked[i] == 0:
            sequences[i] = [i for i in sequences[now]]
            dfs(i)


def BinarySearch(num, nums):
    if len(nums) == 0:
        print("Erorr : list has no element")
        return
    left,right = 0,len(nums)
    while left < right:
        mid  = (left+right)//2
        if num < nums[mid]:
            right = mid
        else:
            left = mid + 1
    return right


def LIS(seq):
    LISs = [seq[0]]
    for i in range(1,len(seq)):
        if seq[i] > LISs[-1]:
            LISs.append(seq[i])
        else:
            right = BinarySearch(seq[i], LISs)
            if LISs[right-1] != seq[i]:
                LISs[right] = seq[i]
    return len(LISs)


tree = []
checked = []
As = []
sequences = []
ans = []


def main():
    global tree,checked,As,sequences,ans
    n = ni()
    As = na()
    tree = [[] for _ in range(n)]#tree[i] = The children of vertex i
    sequences = [[] for _ in range(n)]#sequences[i] = The sequence of a's values that is shortest path to vertex i
    sequences[0] = [As[0]]
    checked = [0 for _ in range(n)]
    ans = [-1 for _ in range(n)]
    for _ in range(n-1):
        u,v = na()
        tree[u-1] += [v-1]
        tree[v-1] += [u-1]
    dfs(0)
    for i in range(n):
        print(ans[i])
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections
import bisect

def f(v):
    #state[v] = 1
    a=As[v]
    idx = bisect.bisect_left(D,a)
    stack.append( (idx,D[idx]) ) # push
    D[idx] = a
    
    ans[v] = bisect.bisect_left(D,float('inf'))

    for u in V[v]:
        # if state[u] == 1: 木構造なので不要
        len_pre=len(stack)
        
        f(u)

        # 巻き戻し
        while len(stack) > len_pre:
            i_pre,d_pre=stack.pop()
            D[i_pre] = d_pre



N=int(input())
As=list(map(int,input().split()))

D=[float('inf')]*N
stack=collections.deque([])
ans=[0]*N
#state=[0]*N

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

f(0)

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

Submission status: Runtime Error

Solution code:
import bisect
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)

Submission status: Runtime Error

Solution code:
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 ans[1:]:
    print(i)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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(v):
    ind = bisect.bisect_left(dp,a[v-1])
    changes.append([ind,dp[ind]])
    dp[ind] = a[v-1]
    ans[v] = bisect.bisect_left(dp,INF)
    
    for i in t[v]:
        if not checked[i]:
            checked[i] = True
            search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
print('\n'.join(map(str,ans[1:])))

Submission status: Runtime Error

Solution code:
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(v):
    ind = bisect.bisect_left(dp,a[v-1])
    changes.append([ind,dp[ind]])
    dp[ind] = a[v-1]
    ans[v] = bisect.bisect_left(dp,INF)
    
    for i in t[v]:
        if not checked[i]:
            checked[i] = True
            search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
print('\n'.join(map(str,ans[1:])))

Submission status: Runtime Error

Solution code:
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 = [1]
changes = []

def search(v):
    ind = bisect.bisect_left(dp,a[v-1])
    changes.append([ind,dp[ind]])
    dp[ind] = a[v-1]
    ans[v] = bisect.bisect_left(dp,INF)
    
    for i in t[v]:
        if i in checked:
            continue
        checked.append(i)
        search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
print('\n'.join(map(str,ans[1:])))

Submission status: Runtime Error

Solution code:
# 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()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
import bisect
import copy
from collections import deque

def main():
    N = int(input())
    a = list(map(int,input().split()))
    INF = 10**12
    
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        u,v = map(int,input().split())
        edge[u-1].append(v-1)
        edge[v-1].append(u-1)
        
    def LIS(dp,num):
        ind = bisect.bisect_left(dp,num)
        ret = dp[ind]
        dp[ind] = num
        return ind,ret
    
    dp = [INF]*(N+2)
    dp[0] = -INF
    dp[1] = a[0]

    ans = [0]*N
    q = deque([])
    
    def DFS(prev,now,dp):
        while q:
            s,t,ind,num = q.pop()
            if t == prev:
                q.append((s,t,ind,num))
                break
            else:
                dp[ind] = num
        ind,num = LIS(dp,a[now])
        ans[now] = ind
        q.append((prev,now,ind,num))
        for fol in edge[now]:
            if fol != prev:
                DFS(now,fol,dp)

    DFS(-1,0,dp)
    print(*ans,sep="\n")
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from pprint import pprint as pp
from pprint import pformat as pf

import math
import bisect

def solve(seq):
    dp = [math.inf] * (len(seq) + 1)
    dp[0] = -1 * math.inf
    for value in seq:
        key = bisect.bisect_left(dp, value)
        dp[key] = value
        print('dp') # debug
        print(dp) # debug
    key = bisect.bisect_left(dp, math.inf)
    return key - 1

class Tree:
    """
    node id starts from 1
    """

    DUMMY = 0 # used as dummy_node_id and dummy_node_value

    def __init__(self, num_node, node_values):
        self.node_values = [-1] + node_values # [0] is dummy
        self.edges = [None] * (num_node + 1) # [0] is dummy, var[a] = set of links
        for i, _ in enumerate(self.edges):
            self.edges[i] = set()
        self.seq = [self.DUMMY] * num_node

        self.dp = [math.inf] * (num_node + 1)
        self.dp[0] = -1 * math.inf
        self.ans = [0] * (num_node + 1) # [0] is dummy


    def node_values(self, node_values):
        self.node_values = [-1] + node_values # [0] is dummy

    def make_edge(self, a, b):
        self.edges[a].add(b)
        self.edges[b].add(a)

    def dps(self, node_id, prev=0, depth=0):
        # process
        value = self.node_values[node_id]
        key = bisect.bisect_left(self.dp, value)
        old_value = self.dp[key]
        self.dp[key] = value
        self.ans[node_id] = max(key, self.ans[prev])
        # recursive
        for to in self.edges[node_id]:
            if to == prev:
                continue
            self.dps(to, node_id, depth + 1)
        # recursive back
        self.dp[key] = old_value

if __name__ == '__main__':
    num_node = int(input())
    node_values = list(map(int, input().split()))
    tree = Tree(num_node, node_values)
    for i in range(num_node - 1):
        frm, to = map(int, input().split())
        tree.make_edge(frm, to)
    tree.dps(1)
    for a in tree.ans[1:]:
        print(a)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from pprint import pprint as pp
from pprint import pformat as pf

import math
from sortedcontainers import SortedList, SortedDict, SortedSet
import bisect

def solve(seq):
    dp = [math.inf] * (len(seq) + 1)
    dp[0] = -1 * math.inf
    for value in seq:
        key = bisect.bisect_left(dp, value)
        dp[key] = value
        print('dp') # debug
        print(dp) # debug
    key = bisect.bisect_left(dp, math.inf)
    return key - 1

class Tree:
    """
    node id starts from 1
    """

    DUMMY = 0 # used as dummy_node_id and dummy_node_value

    def __init__(self, num_node, node_values):
        self.node_values = [-1] + node_values # [0] is dummy
        self.edges = [None] * (num_node + 1) # [0] is dummy, var[a] = set of links
        for i, _ in enumerate(self.edges):
            self.edges[i] = set()
        self.seq = [self.DUMMY] * num_node

        self.dp = [math.inf] * (num_node + 1)
        self.dp[0] = -1 * math.inf
        self.ans = [0] * (num_node + 1) # [0] is dummy


    def node_values(self, node_values):
        self.node_values = [-1] + node_values # [0] is dummy

    def make_edge(self, a, b):
        self.edges[a].add(b)
        self.edges[b].add(a)

    def dps(self, node_id, prev=0, depth=0):
        # process
        value = self.node_values[node_id]
        key = bisect.bisect_left(self.dp, value)
        old_value = self.dp[key]
        self.dp[key] = value
        self.ans[node_id] = max(key, self.ans[prev])
        # recursive
        for to in self.edges[node_id]:
            if to == prev:
                continue
            self.dps(to, node_id, depth + 1)
        # recursive back
        self.dp[key] = old_value

if __name__ == '__main__':
    num_node = int(input())
    node_values = list(map(int, input().split()))
    tree = Tree(num_node, node_values)
    for i in range(num_node - 1):
        frm, to = map(int, input().split())
        tree.make_edge(frm, to)
    tree.dps(1)
    for a in tree.ans[1:]:
        print(a)



    print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_right
from copy import deepcopy
n=int(input())
a=list(map(int,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)
visited=[True]*n
lis=[[] for _ in range(n)]
def dfs():
    stack=deque([0])
    visited[0]=False
    lis[0]=[a[0]]
    while stack:
        x=stack.pop()
        for nx in edge[x]:
            if visited[nx]:
                if a[nx]>lis[x][-1]:
                    lis[nx]=lis[x]+[a[nx]]
                else:
                    idx=bisect_right(lis[x],a[nx])
                    cur=deepcopy(lis[x])
                    cur[idx]=a[nx]
                    lis[nx]=cur
                visited[nx]=False
                stack.append(nx)
    return
dfs()
for i in range(n):
    print(len(lis[i]))

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_right
from copy import deepcopy
n=int(input())
a=list(map(int,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)
visited=[True]*n
lis=[[] for _ in range(n)]
def dfs():
    stack=deque([0])
    visited[0]=False
    lis[0]=[a[0]]
    while stack:
        x=stack.pop()
        for nx in edge[x]:
            if visited[nx]:
                if a[nx]>lis[x][-1]:
                    lis[nx]=lis[x]+[a[nx]]
                else:
                    idx=bisect_right(cur,a[nx])
                    cur=deepcopy(lis[x])
                    cur[idx]=a[nx]
                    lis[nx]=cur
                visited[nx]=False
                stack.append(nx)
    return
dfs()
for i in range(n):
    print(len(lis[i]))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf


import math

def binary_search(l, value, over):
    """
    flg_same: bool

    l = [0, 10, 20]
    first_over(l, 9) # 1, 10
    first_over(l, 10) # 2, 20
    first_over(l, 10, True) # 1, 10
    first_over(l, -10) # 0, 0
    first_over(l, 100) # None, None
    """
    # assert: l is sorted
    if len(l) == 0:
        return None, None
    b = 0 # bottom
    t = len(l) - 1 # top
    if not over(l[t], value):
        return None, None
    while not (b == t):
        head = b + ((t - b) // 2)
        if over(l[head], value):
            t = head
        else:
            b = head + 1
    return b, l[b]

def first_over_or_same(l, value):
    def over_or_same(a, b):
        return a >= b
    return binary_search(l, value, over_or_same)

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.last_not_inf = 0
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        self.dp.append(math.inf)
        self.history.append(None)
        self.use(value)
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        d = self.history[-1]
        self.dp[d.dp_key] = d.before_value

    def use(self, value):
        key, over_value = first_over_or_same(self.dp, value)
        if key is not None and over_value != value:
            self.history[-1] = SolverLIS.Diff(key, self.dp[key])
            self.dp[key] = value


    def get_longest_increasing_subsequence_size(self):
        key, value = first_over_or_same(self.dp, math.inf)
        if key is None:
            return len(self.dp) - 1
        return key - 1


class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef):
        # process
        ans[node] = solver.append_last(node_values[node])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node)
        # exit recursive
        solver.remove_last()
    _dps(1, 0)
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

    for a in path_list[1:]:
        print(a)








    #print('\33[32m' + 'end' + '\033[0m')

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_right
from copy import deepcopy
n=int(input())
a=list(map(int,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)
visited=[True]*n
lis=[[] for _ in range(n)]
def dfs():
    stack=deque([0])
    visited[0]=False
    lis[0]=[a[0]]
    while stack:
        x=stack.pop()
        for nx in edge[x]:
            cur=deepcopy(lis[x])
            if visited[nx]:
                if a[nx]>cur[-1]:
                    cur.append(a[nx])
                else:
                    idx=bisect_right(cur,a[nx])
                    cur[idx]=a[nx]
                lis[nx]=cur
                visited[nx]=False
                stack.append(nx)
    return
dfs()
for i in range(n):
    print(len(lis[i]))

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_right
from copy import deepcopy
n=int(input())
a=list(map(int,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)
visited=[True]*n
lis=[[] for _ in range(n)]
def dfs():
    stack=deque([0])
    visited[0]=False
    lis[0]=[a[0]]
    while stack:
        x=stack.pop()
        for nx in edge[x]:
            cur=deepcopy(lis[x])
            if visited[nx]:
                if a[nx]>cur[-1]:
                    cur.append(a[nx])
                else:
                    idx=bisect_right(cur,a[nx])
                    cur[idx]=a[nx]
                lis[nx]=cur
                visited[nx]=False
                stack.append(nx)
dfs()
for i in range(n):
    print(len(lis[i]))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf


import math

def binary_search(l, value, over):
    """
    flg_same: bool

    l = [0, 10, 20]
    first_over(l, 9) # 1, 10
    first_over(l, 10) # 2, 20
    first_over(l, 10, True) # 1, 10
    first_over(l, -10) # 0, 0
    first_over(l, 100) # None, None
    """
    # assert: l is sorted
    if len(l) == 0:
        return None, None
    b = 0 # bottom
    t = len(l) - 1 # top
    if not over(l[t], value):
        return None, None
    while not (b == t):
        head = b + ((t - b) // 2)
        if over(l[head], value):
            t = head
        else:
            b = head + 1
    return b, l[b]

def first_over_or_same(l, value):
    def over_or_same(a, b):
        return a >= b
    return binary_search(l, value, over_or_same)

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.last_not_inf = 0
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        self.dp.append(math.inf)
        self.history.append(None)
        self.use(value)
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        d = self.history[-1]
        self.dp[d.dp_key] = d.before_value

    def use(self, value):
        key, over_value = first_over_or_same(self.dp, value)
        if key is not None and over_value != value:
            self.history[-1] = SolverLIS.Diff(key, self.dp[key])
            self.dp[key] = value


    def get_longest_increasing_subsequence_size(self):
        def from_end():
            length = len(self.dp) - 1
            while length >= 0:
                value = self.dp[length]
                if value is not math.inf and value > 0:
                    self.last_not_inf = length
                    return
                # for next
                length -= 1
            self.last_not_inf = 0
        if not (len(self.dp) > self.last_not_inf):
            from_end()
        if self.dp[self.last_not_inf] is math.inf:
            self.last_not_inf -= 1
        elif (len(self.dp) > self.last_not_inf + 1) and self.dp[self.last_not_inf + 1] is not math.inf:
            self.last_not_inf += 1
        return self.last_not_inf



class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef):
        # process
        ans[node] = solver.append_last(node_values[node])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node)
        # exit recursive
        solver.remove_last()
    _dps(1, 0)
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

    for a in path_list[1:]:
        print(a)








    #print('\33[32m' + 'end' + '\033[0m')

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf


import math

def binary_search(l, value, over):
    """
    flg_same: bool

    l = [0, 10, 20]
    first_over(l, 9) # 1, 10
    first_over(l, 10) # 2, 20
    first_over(l, 10, True) # 1, 10
    first_over(l, -10) # 0, 0
    first_over(l, 100) # None, None
    """
    # assert: l is sorted
    if len(l) == 0:
        return None, None
    b = 0 # bottom
    t = len(l) - 1 # top
    if not over(l[t], value):
        return None, None
    while not (b == t):
        head = b + ((t - b) // 2)
        if over(l[head], value):
            t = head
        else:
            b = head + 1
    return b, l[b]

def first_over_or_same(l, value):
    def over_or_same(a, b):
        return a >= b
    return binary_search(l, value, over_or_same)

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        return -1
        self.dp.append(math.inf)
        self.history.append(None)
        self.use(value)
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        d = self.history[-1]
        self.dp[d.dp_key] = d.before_value

    def use(self, value):
        key, over_value = first_over_or_same(self.dp, value)
        if key is not None and over_value != value:
            self.history[-1] = SolverLIS.Diff(key, self.dp[key])
            self.dp[key] = value


    def get_longest_increasing_subsequence_size(self):
        length = len(self.dp) - 1
        while length >= 0:
            value = self.dp[length]
            if value is not math.inf and value > 0:
                return length
            # for next
            length -= 1
        return 0


class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef):
        # process
        ans[node] = solver.append_last(node_values[node])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node)
        # exit recursive
        solver.remove_last()
    _dps(1, 0)
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

    for a in path_list[1:]:
        print(a)








    #print('\33[32m' + 'end' + '\033[0m')