Problem p02698 (python)

Fixed submission:
import sys
import bisect  # 二分法


MAX_N = 200005
INF = 10**9 + 5

sys.setrecursionlimit(MAX_N)

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]
E = [[] for _ in range(N)]  # 辺の情報

for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    E[u-1].append(v-1)
    E[v-1].append(u-1)

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

def dfs(u,r=-1):

    # u を訪れたときの処理
    i = bisect.bisect_left(lis, A[u])  # 
    old = lis[i]  # 書き換え前の値を一時保存
    lis[i] = A[u]

    for v in E[u]:
        if v == r: continue  # 親は無視

        dfs(v,u)
    
    ans[u] = bisect.bisect_left(lis,INF-1)
    lis[i] = old  # 書き換え前の状態に戻す

dfs(0)
for i in range(N):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
import sys
import bisect  # 二分法

MAX_N = 200005
INF = 10**9 + 5

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]
E = [[] for _ in range(N)]  # 辺の情報

for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    E[u-1].append(v-1)
    E[v-1].append(u-1)

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

def dfs(u,r=-1):

    # u を訪れたときの処理
    i = bisect.bisect_left(lis, A[u])  # 
    old = lis[i]  # 書き換え前の値を一時保存
    lis[i] = A[u]

    for v in E[u]:
        if v == r: continue  # 親は無視

        dfs(v,u)
    
    ans[u] = bisect.bisect_left(lis,INF-1)
    lis[i] = old  # 書き換え前の状態に戻す

dfs(0)
for i in range(N):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
import sys
import bisect  # 二分法

MAX_N = 200005
INF = 10**9 + 5

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]
E = [[] for _ in range(N)]  # 辺の情報

for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    E[u-1].append(v-1)
    E[v-1].append(u-1)

lis = [INF] * N
lis[0] = 1
ans = [0] * N 

def dfs(u,r=-1):

    # u を訪れたときの処理
    i = bisect.bisect_left(lis, A[u])  # 
    old = lis[i]  # 書き換え前の値を一時保存
    lis[i] = A[u]

    for v in E[u]:
        if v == r: continue  # 親は無視

        dfs(v,u)
    
    ans[u] = bisect.bisect_left(lis,INF-1)
    lis[i] = old  # 書き換え前の状態に戻す

dfs(0)
for i in range(N):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
import sys
import bisect

def dfs(u,k,r=0):

    B = [A[u]]
    if u == k:
        return B, True

    for v in E[u]:
        if v == r: continue  # 親は無視

        Ap, has_k = dfs(v,k,u)
        if has_k:
            B.extend(Ap)
            return B, True

    return [], False

def lis(A):
    
    dp = [A[0]]

    if len(A) == 1:
        return 1

    for i in range(len(A)):
        if A[i] > dp[-1]:
            dp.append(A[i])
        else:
            tmp = bisect.bisect_left(dp, A[i])
            dp[bisect.bisect_left(dp, A[i])] = A[i]
    
    return len(dp)

if __name__ == "__main__":

    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]
    E = [[] for _ in range(N)]  # 辺の情報
    for _ in range(N-1):
        u, v = map(int, sys.stdin.readline().split())
        E[u-1].append(v-1)
        E[v-1].append(u-1)

    for i in range(N):
        C, _ = dfs(0,i)
        print(lis(C))

Buggy submission (verdict: Runtime Error):
import sys
import bisect

def dfs(u,k,r=0):

    B = [A[u]]
    if u == k:
        return B, True

    for v in E[u]:
        if v == r: continue  # 親は無視

        Ap, has_k = dfs(v,k,u)
        if has_k:
            B.extend(Ap)
            return B, True

    return [], False

def lis(A):
    
    dp = [A[0]]

    if len(A) == 1:
        return 1

    for i in range(len(A)):
        if A[i] > dp[-1]:
            dp.append(A[i])
        else:
            tmp = bisect.bisect_left(dp, A[i])
            dp[bisect.bisect_left(dp, A[i])] = A[i]
    
    return len(dp)

if __name__ == "__main__":

    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]
    E = [[] for _ in range(N)]  # 辺の情報
    for _ in range(N-1):
        u, v = map(int, sys.stdin.readline().split())
        E[u-1].append(v-1)
        E[v-1].append(u-1)

    for i in range(N):
        C, _ = dfs(0,i)
        print(lis(C))