Problem p02698 (python)

Fixed submission:
from collections import deque
from bisect import bisect_left

INF = 10**9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    G[u-1].append(v-1)
    G[v-1].append(u-1)

LIS = [INF] * N
ans = [0] * N

stack = deque()
stack.append((0, None, None)) # (current_node, prev_node, old_val)
while stack:
    c_node, p_node, old_val = stack.pop()

    if c_node == -1:
        LIS[p_node] = old_val
        continue

    a = A[c_node]
    idx = bisect_left(LIS, a)
    old_val = LIS[idx]
    LIS[idx] = a 
    
    ans[c_node] = bisect_left(LIS, INF)

    stack.append((-1, idx, old_val))

    for next_node in G[c_node]:
        if next_node != p_node:
            stack.append((next_node, c_node, old_val))

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

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_left

def dfs(v, p=-1):
    a = A[v]
    idx = bisect_left(LIS, a)
    old_val = LIS[idx]
    LIS[idx] = a

    ans[v] = bisect_left(LIS, INF)

    for u in G[v]:
        if u == p:
            continue
        dfs(u, v)
    
    LIS[idx] = old_val

INF = 10**9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    G[u-1].append(v-1)
    G[v-1].append(u-1)

LIS = [INF] * N
ans = [0] * N

dfs(0)

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

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_left

INF = 10**9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    if u > v:
        u, v = v, u
    G[u-1].append(v-1)
LIS = [INF] * N
ans = [0] * N

stack = deque()
stack.append((0, None, None)) # (current_node, prev_node, old_val)
while stack:
    c_node, p_node, old_val = stack.pop()

    if c_node == -1:
        LIS[p_node] = old_val
        continue

    a = A[c_node]
    idx = bisect_left(LIS, a)
    old_val = LIS[idx]
    LIS[idx] = a 
    
    ans[c_node] = bisect_left(LIS, INF)

    stack.append((-1, idx, old_val))

    for next_node in G[c_node]:
        stack.append((next_node, c_node, old_val))
    
    print(LIS)

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

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_left

INF = 10**9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    G[u-1].append(v-1)
LIS = [INF] * N
ans = [0] * N

stack = deque()
stack.append((0, None, None))
while stack:
    c_node, p_node, old_val = stack.pop()

    if c_node == -1:
        print(c_node, p_node, old_val)
        LIS[p_node] = old_val
        print(c_node, LIS)
        continue

    a = A[c_node]
    idx = bisect_left(LIS, a)
    old_val = LIS[idx]
    LIS[idx] = a 
    
    ans[c_node] = bisect_left(LIS, INF)
    print(c_node, LIS)

    stack.append((-1, idx, old_val))

    for next_node in G[c_node]:
        stack.append((next_node, c_node, old_val))

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

Buggy submission (verdict: Runtime Error):
import bisect

N = int(input())
A = list(map(int, input().split()))
tree = [{'par': 0, 'LIS': []} for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    tree[v-1]['par'] = u - 1

tree[0]['LIS'] = [A[0]]
for i in range(1, N):
    a = A[i]
    par = tree[i]['par']
    LIS = tree[par]['LIS'][:]
    if a > LIS[-1]:
        LIS.append(a)
    else:
        LIS[bisect.bisect_left(LIS, a)] = a
    tree[i]['LIS'] = LIS[:]
for i in range(N):
    print(len(tree[i]['LIS']))