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:
#!/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):
        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')

Submission status: Runtime Error

Solution code:
# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit = 10**7

INF = 10**18

n = int(input())
a = list(int(x) for x in 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)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    #if ans[par] <= idx:
    #    ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    #else:
    #    ans[now] = ans[par]
    ans[now] = bisect.bisect_left(dp, INF)

    for i in g[now]:
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
#dp = [-INF] + [INF] * n
dp = [INF] * n
dfs(0,-1)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit = 10**10

INF = 10**10

n = int(input())
a = list(int(x) for x in 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)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    #if ans[par] <= idx:
    #    ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    #else:
    #    ans[now] = ans[par]
    ans[now] = bisect.bisect_left(dp, INF)

    for i in g[now]:
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
#dp = [-INF] + [INF] * n
dp = [INF] * n
dfs(0,-1)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit = 10**10

INF = 10**10

n = int(input())
a = list(int(x) for x in 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)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        #print('i',i)
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * (n+1)
dfs(0,-1)
for a in ans:
    print(a)

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


#ダイクストラ(参照:https://gside.org/blog/2019/12/01/, https://ta7uw.hatenablog.com/entry/2018/09/30/222102)
class Node(object):#頂点
    def __init__(self,  value: int):
        self.value = value

    def getValue(self) -> int:
        return self.value

    def __str__(self):
        return str(self.value)

    def __lt__(seif, other):
        return None


class WeightedEdge(object):#重み付き枝
    def __init__(self, src: Node, dest: Node, weight: int):
        self.src = src
        self.dest = dest
        self.weight = weight

    def getSource(self) -> Node:
        return self.src

    def getDestination(self) -> Node:
        return self.dest

    def getWeight(self) -> int: 
        return self.weight

    def __str__(self):
        return str(self.src.getValue()) + '->('  + str(self.getWeight()) + ')->' + str(self.dest.getValue())


class Digraph(object):#有向グラフ
    def __init__(self):
        self.nodes = []
        self.edges = {}
        self.size = 0

    def addNode(self, node: Node):
        if node in self.nodes:
            raise ValueError('Duplicate node')
        else:
            self.nodes.append(node)
            self.edges[node] = []
            self.size += 1
    
    def addEdge(self, edge: WeightedEdge):
        src = edge.getSource()
        dest = edge.getDestination()
        weight = edge.getWeight()
        if not (src in self.nodes and dest in self.nodes):
            raise ValueError('Node not a graph')

        self.edges[src].append((weight, dest))
    
    def childrenOf(self, node: Node) -> list:#element : tuple
        return self.edges[node]
    
    def __str__(self):
        result = ''
        for src in self.nodes:
            for weightdest in self.edges[src]:
                dest  = weightdest[1]
                result += str(src.getValue()) + '->' + str(dest.getValue()) + '\n'
        return result[:-1]


class RingBuffer(object):
    def __init__(self, size: int):
        self.ringsize = size
        self.size = 0
        self.ring = [None]*size
        self.head = 0
        self.tail = 0
    def enring(self, a: int):
        if self.tail != self.head or self.ring[self.tail] == None:
            self.ring[self.tail] = a
            self.tail += 1
            self.tail %= self.ringsize
            self.size += 1
        else:
            print('Error : This Ring Buffer is full.')
    def dering(self):
        if self.head != self.tail:
            tmp = self.ring[self.head]
            self.ring[self.head] = None # なくてもよい．
            self.head += 1
            self.head %= self.ringsize
            self.size -= 1
            return tmp
        else:
            print(self.head, self.tail)
            print('Error : This Ring Buffer is empty.')


def getPath(goalNode, prev):
    path = [goalNode]
    dest = goalNode.getValue()
    while prev[dest] != float('inf'):
        path.append(prev[dest])
        dest = prev[dest].getValue()
    return list(reversed(path))


def Dijkstra(graph: Digraph, startNode: Node, goalNode: Node = None) -> list:#Reture a list that has minimum distances from the start point to each point
    dist = [float('inf') for _ in range(graph.size)]
    prev = [float('inf') for _ in range(graph.size)]

    dist[startNode.getValue()] = 0
    srcque = RingBuffer(graph.size)
    costque = RingBuffer(graph.size)
    
    srcque.enring(startNode)
    costque.enring(0)
    while srcque.size != 0:
        srcNode = srcque.dering()
        prev_cost = costque.dering()

        if dist[srcNode.getValue()] < prev_cost:
            continue
        
        for cost, destNode  in graph.childrenOf(srcNode):
            if cost != float('inf') and dist[destNode.getValue()] > dist[srcNode.getValue()] + cost:
                dist[destNode.getValue()] = dist[srcNode.getValue()] + cost
                srcque.enring(destNode)
                costque.enring(dist[destNode.getValue()])
                prev[destNode.getValue()] = srcNode
    if goalNode == None:
        return dist, prev
    else:
        return getPath(goalNode, prev)


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:
            LISs[BinarySearch(seq[i], LISs)] = seq[i]
    return len(LISs)


def main():
    n = ni()
    As = na()
    d = Digraph()
    Nodes = [Node(i) for i in range(n)]
    for node in Nodes:
        d.addNode(node)
    for _ in range(n-1):
        u,v = na()
        d.addEdge(WeightedEdge(Nodes[u-1],Nodes[v-1],1))
        d.addEdge(WeightedEdge(Nodes[v-1],Nodes[u-1],1))
    dist, prev = Dijkstra(d, Nodes[0])
    for k in range(n):
        ss = [As[node.getValue()] for node in getPath(Nodes[k], prev)]
        print(LIS(ss))
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

if n % 2 == 1:
    for i in range(1, m+1):
        print(i, n-i)
else:
    half = min(n // 4, m+1)
    for i in range(1, half):
        print(i, n-i)
    for i in range(half, m+1):
        print(i+1, n-i)

Submission status: Runtime Error

Solution code:
# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit = 10**10

INF = 10**10

n = int(input())
a = list(int(x) for x in 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)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        #print('i',i)
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * (n+1)
dfs(0,-1)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
# F - LIS on Tree
import bisect
import sys
sys.setrecursionlimit = 10**6

INF = 10**10

n = int(input())
a = list(int(x) for x in 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)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        #print('i',i)
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * (n+1)
dfs(0,-1)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
# F - LIS on Tree
import bisect

INF = 10**10

n = int(input())
a = list(int(x) for x in 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)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        #print('i',i)
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * n
dfs(0,-1)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
# F - LIS on Tree
import bisect

INF = 10**18

n = int(input())
a = list(int(x) for x in 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)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        #print('i',i)
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * (n+1)
dfs(0,-1)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] + lr()  # 1-indexed
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (N+1)  # 1-indexed
INF = 10 ** 6
parent = [-1] * (N+1)

def dfs(n, arr):
    """arrはLISのリスト、answerのリストを更新してから子にarrを渡す"""
    i = bisect_left(arr, INF)
    answer[n] = i
    for c in graph[n]:
        if c == parent[n]:
            continue
        parent[c] = n
        new = arr[:]
        i = bisect_left(new, A[c])
        new[i] = A[c]
        dfs(c, new)

B = [INF] * (N+1)
B[0] = A[1]
dfs(1, B)
for a in answer[1:]:
    print(a)

Submission status: Runtime Error

Solution code:
# F - LIS on Tree
import bisect

INF = 10**18

n = int(input())
a = list(int(x) for x in 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)

def dfs(now, par):
    idx = bisect.bisect_left(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        #print('i',i)
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * n
dfs(0,-1)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] + lr()  # 1-indexed
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (N+1)  # 1-indexed
INF = 10 ** 6
parent = [0] * (N+1)

def dfs(n, arr):
    """arrはLISのリスト、answerのリストを更新してから子にarrを渡す"""
    i = bisect_left(arr, INF)
    answer[n] = i
    for c in graph[n]:
        if c == parent[n]:
            continue
        parent[c] = n
        new = arr[:]
        i = bisect_left(new, A[c])
        new[i] = A[c]
        dfs(c, new)

B = [INF] * N
B[0] = 0
dfs(1, B)
for a in answer[1:]:
    print(a)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] + lr()  # 1-indexed
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (N+1)  # 1-indexed
INF = 10 ** 6
parent = [0] * (N+1)

def dfs(n, arr):
    """arrはLISのリスト、answerのリストを更新してから子にarrを渡す"""
    i = bisect_left(arr, INF)
    answer[n] = i
    for c in graph[n]:
        if c == parent[n]:
            continue
        parent[c] = n
        new = arr[:]
        i = bisect_left(new, A[c])
        new[i] = A[c]
        dfs(c, new)

B = [INF] * N
B[0] = 0
dfs(1, B)
for a in answer[1:]:
    print(a)

Submission status: Runtime Error

Solution code:
# F - LIS on Tree
import bisect

INF = 10**18

n = int(input())
a = list(int(x) for x in 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)

def dfs(now, par):
    idx = bisect.bisect_right(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        #print('i',i)
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * n
dfs(0,-1)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
# F - LIS on Tree
import bisect

INF = 10**10

n = int(input())
a = list(int(x) for x in 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)

def dfs(now, par):
    idx = bisect.bisect_right(dp, a[now])    
    tmp = dp[idx]
    dp[idx] = a[now]
    #print(dp)
    #print('now',now)
    # 親のLIS以上であれば、その値で更新
    if ans[par] <= idx:
        ans[now] = idx
    # そうでなければ親のLISを引き継ぐ
    else:
        ans[now] = ans[par]

    for i in g[now]:
        #print('i',i)
        if i!=par:
            # 次にみる頂点と、自分（親）の情報を渡す
            dfs(i, now)
    dp[idx] = tmp

ans = [0] * n
dp = [-INF] + [INF] * n
dfs(0,-1)
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
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)]

    def dfs(node, length=0, parent=None):
        seen[node] = True
        stack.append(node)
        length += 1
        
        if parent == None:
            dp[node].append(A[node])
        else:
            for val in dp[parent][1:]:
                dp[node].append(val)
            for i, val in enumerate(dp[node][1:], 1):
                if val > A[node]:
                    dp[node][i] = A[node]
                    break
            if dp[node][-1] < A[node]:
                dp[node].append(A[node])
            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):
        try:
            s = dp[i][1:].index(float('inf'))
            print(s)
        except:
            print(len(dp[i][1:]))


if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
n = int(input())
aa = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

dp = [10 ** 18] * (n + 10)
dp[0] = 0
ans1 = [0] * n
ans2 = [0] * n


def dfs(i=0, r=-1):
    mi = 0
    ma = n
    while mi != ma:
        mm = (mi + ma) // 2
        if dp[mm] >= aa[i]:
            ma = mm
        else:
            mi = mm + 1

    be = dp[mi]
    dp[mi] = min(dp[mi], aa[i])
    ans1[i] = mi
    ans2[i] = max(ans1[i], ans2[r])

    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)

    dp[mi] = be


dfs()
for i in ans2:
    print(i)

Submission status: Runtime Error

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
ali = li()
A = [[] for _ in range(n)]
for _ in range(n-1):
    u,v = mi()
    A[u-1].append(v-1) 
    A[v-1].append(u-1) 

inf = 10**9 + 5
dpans = [inf]*n
dptmp = [inf]*(n+1)

from bisect import bisect_left as bl
'''index  =  bl(list,num)'''

def df(ima,pre):
    tmp = ali[ima]
    index = bl(dptmp,tmp)
    mae = dptmp[index]
    dptmp[index] = tmp

    for i in A[ima]:
        if i != pre:
            df(i,ima)
        #print(dptmp)
    dpans[ima] = bl(dptmp,inf)

    dptmp[index] = mae


df(0,0)
for i in range(n):
    print(dpans[i])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

inf = 10 ** 6
lis = [inf] * (N * 2)
s = [1]
vis = [0] * (N + 1)
euler = []
while len(s):
  x = s.pop()
  if x >= 0:
    vis[x] = 1
    euler.append(x)
    for y in e[x]:
      if vis[y]: continue
      s.append(~y)
      s.append(y)
  else: euler.append(x)

rollback = []
res = [0] * (N + 1)
for x in euler:
  if x >= 0:
    y = bl(lis, a[x])
    rollback.append((y, lis[y]))
    lis[y] = a[x]
    res[x] = bl(lis, inf)
  else:
    y, v = rollback.pop()
    lis[y] = v

for r in res[1: ]: print(r)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

inf = 10 ** 6
lis = [inf] * (N + 2)
s = [1]
vis = [0] * (N + 1)
euler = []
while len(s):
  x = s.pop()
  if x >= 0:
    vis[x] = 1
    euler.append(x)
    for y in e[x]:
      if vis[y]: continue
      s.append(~y)
      s.append(y)
  else: euler.append(x)

rollback = []
res = [0] * (N + 1)
for x in euler:
  if x >= 0:
    y = bl(lis, a[x])
    rollback.append((y, lis[y]))
    lis[y] = a[x]
    res[x] = bl(lis, inf)
  else:
    y, v = rollback.pop()
    lis[y] = v

for r in res[1: ]: print(r)

Submission status: Runtime Error

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
ali = li()
A = [[] for _ in range(n)]
for _ in range(n-1):
    u,v = mi()
    A[u-1].append(v-1) 

inf = 10**9 + 5
dpans = [inf]*n
dptmp = [inf]*(n+1)

from bisect import bisect_left as bl
'''index  =  bl(list,num)'''

def df(ima):
    tmp = ali[ima]
    index = bl(dptmp,tmp)
    mae = dptmp[index]
    dptmp[index] = tmp

    for i in A[ima]:
        df(i)
        #print(dptmp)
    dpans[ima] = bl(dptmp,inf)

    dptmp[index] = mae


df(0)
for i in range(n):
    print(dpans[i])

Submission status: Runtime Error

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
ali = li()
A = [[] for _ in range(n)]
for _ in range(n-1):
    u,v = mi()
    A[u-1].append(v-1) 

inf = 10**9 + 5
dpans = [inf]*n
dptmp = [inf]*n

from bisect import bisect_left as bl
'''index  =  bl(list,num)'''

def df(ima):
    tmp = ali[ima]
    index = bl(dptmp,tmp)
    mae = dptmp[index]
    dptmp[index] = tmp

    for i in A[ima]:
        df(i)
        #print(dptmp)
    dpans[ima] = bl(dptmp,inf)

    dptmp[index] = mae


df(0)
for i in range(n):
    print(dpans[i])

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

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):
        self.dp.append(math.inf)
        self.history.append([])
        self.use(value, len(self.dp))
        return self.get_longest_increasing_subsequence_size()

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

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

    def use(self, value, loop_end):
        for length, last_value in enumerate(self.dp[:loop_end + 1]):
            if last_value < value:
                self.update_dp(length + 1, value)


    def update_dp(self, length, value):
        if value < self.dp[length]:
            self.history[-1].append(SolverLIS.Diff(length, self.dp[length]))
            self.dp[length] = 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 iter_node_value(path, node_values):
    for node in path:
        yield node_values[node]

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, path):
        path.append(node)
        # process
        value_list = list(iter_node_value(path, node_values))
        #print('value_list, node') # debug
        #print(value_list, node) # debug
        #ans[node] = longest_increment_size(value_list)
        ans[node] = solver.append_last(value_list[-1])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node, path)
        # exit recursive
        solver.remove_last()
        path.pop(-1)
    _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')