Problem p02698 (python)

Fixed submission:
from bisect import bisect_left


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    tree = [list() for _ in range(N)]
    for _ in range(N-1):
        u, v = [int(x) for x in input().split()]
        u -= 1
        v -= 1
        tree[u].append(v)
        tree[v].append(u)

    ans = [1] * N

    # dfs
    def dfs(u, par):
        nonlocal ans
        nonlocal dp
        pos = bisect_left(dp, A[u])
        old = dp[pos]
        dp[pos] = A[u]

        ans[u] = bisect_left(dp, float("inf")) - 1

        for v in tree[u]:
            if v == par:
                continue
            dfs(v, u)

        dp[pos] = old

    dp = [float("inf")] * (N+1)
    dp[0] = float("-inf")
    dfs(0, -1)

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


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**6)
    main()

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


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    tree = [list() for _ in range(N)]
    for _ in range(N-1):
        u, v = [int(x) for x in input().split()]
        u -= 1
        v -= 1
        tree[u].append(v)
        tree[v].append(u)

    ans = [1] * N

    # dfs
    def dfs(u, par, dp: list):
        if A[u] > dp[-1]:
            dp.append(A[u])
        else:
            dp[bisect_left(dp, A[u])] = A[u]
        ans[u] = max(ans[u], len(dp))
        for v in tree[u]:
            if v != par:
                dfs(v, u, dp)
                if dp:
                    val = dp.pop()
                    if val < A[u]:
                        dp.append(A[u])

    dfs(0, -1, [A[0]])

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



if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(2*(10**5)+1)
    main()

Buggy submission (verdict: Runtime Error):


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    tree = [list() for _ in range(N)]
    for _ in range(N-1):
        u, v = [int(x) for x in input().split()]
        u -= 1
        v -= 1
        tree[u].append(v)
        tree[v].append(u)

    # print(tree)

    ans = [1] * N
    # dfs
    from bisect import bisect_left
    def dfs(u, par, dp: list):
        if A[u] > dp[-1]:
            dp.append(A[u])
        else:
            dp[bisect_left(dp, A[u])] = A[u]
        ans[u] = max(ans[u], len(dp))
        for v in tree[u]:
            if v != par:
                dfs(v, u, dp)
                val = dp.pop()
                if val < A[u]:
                    dp.append(A[u])

    dfs(0, -1, [A[0]])

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



if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(2*(10**5)+1)
    main()

Buggy submission (verdict: Runtime Error):


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    tree = [list() for _ in range(N)]
    for _ in range(N-1):
        u, v = [int(x) for x in input().split()]
        u -= 1
        v -= 1
        tree[u].append(v)
        tree[v].append(u)

    # print(tree)

    ans = [1] * N
    # dfs
    from bisect import bisect_left
    def dfs(u, par, dp: list):
        if A[u] > dp[-1]:
            dp.append(A[u])
        else:
            dp[bisect_left(dp, A[u])] = A[u]
        ans[u] = max(ans[u], len(dp))
        for v in tree[u]:
            if v != par:
                dfs(v, u, dp)
                val = dp.pop()
                if val < A[u]:
                    dp.append(A[u])

    dfs(0, -1, [A[0]])

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



if __name__ == '__main__':
    main()