Problem p02698 (python)

Fixed submission:
# 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()

Buggy submission (verdict: Runtime Error):
# 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)+1], 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)


    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()

Buggy submission (verdict: Runtime Error):
# 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()

Buggy submission (verdict: Runtime Error):
# 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()