Problem p02698 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for x, y in zip(u, v):
        g.add_edge(x-1, y-1)

    ans = [0]*N

    dp = [INF]*N
    event = []
    var = {"last": 0}

    def dfs(curr, par):
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            if dp[i] == INF:
                var["last"] = i
            event.append((curr, i, dp[i]))
            dp[i] = a[curr]

        ans[curr] = var["last"]+1

        for child, w in g.E[curr]:
            if child == par:
                continue
            dfs(child, curr)

        c, i, v = event[-1]
        if c == curr:
            dp[i] = v
            if v == INF:
                var["last"] = i-1
            event.pop()

    dfs(0, -1)
    print(*ans, sep="\n")

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, u, v)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def make_order(g, v):
    seen = [False]*g.N
    pre_order = [-1]*g.N
    post_order = [-1]*g.N
    counters = {"pre": 0, "post": 0}

    parent = [-1]*g.N

    def recur(v):
        pre_order[counters["pre"]] = v
        counters["pre"] += 1

        seen[v] = True
        for to, w in g.E[v]:
            if seen[to] == True:
                continue
            parent[to] = v
            recur(to)

        post_order[counters["post"]] = v
        counters["post"] += 1

    recur(v)
    return pre_order, post_order


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for x, y in zip(u, v):
        g.add_edge(x-1, y-1)

    ans = [0]*N

    dp = [INF]*N
    event = []

    pre_order, post_order = make_order(g, 0)
    # print(pre_order, post_order, parent, sep="\n")
    post_order += [-1]
    post = 0
    seen = [False]*(N+10)
    # return

    for i, curr in enumerate(pre_order):
        # print(i, curr, dp, event)
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            event.append((curr, i, dp[i]))
            dp[i] = a[curr]

        ans[curr] = len(dp[:bisect_left(dp, INF)])
        seen[curr] = True

        while seen[post_order[post]]:
            c, i, v = event.pop()
            dp[i] = v
            post += 1

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, u, v)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def make_order(g, v):
    seen = [False]*g.N
    pre_order = [-1]*g.N
    post_order = [-1]*g.N
    counters = {"pre": 0, "post": 0}

    parent = [-1]*g.N

    def recur(v):
        pre_order[counters["pre"]] = v
        counters["pre"] += 1

        seen[v] = True
        for to, w in g.E[v]:
            if seen[to] == True:
                continue
            parent[to] = v
            recur(to)

        post_order[counters["post"]] = v
        counters["post"] += 1

    recur(v)
    return pre_order, post_order, parent


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for x, y in zip(u, v):
        g.add_edge(x-1, y-1)

    ans = [0]*N

    dp = [INF]*N
    event = []

    pre_order, post_order, parent = make_order(g, 0)
    # print(pre_order, post_order, parent, sep="\n")
    post_order += [N]
    post = 0
    seen = [False]*(N+1)
    # return

    for i, curr in enumerate(pre_order):
        # print(i, curr, dp, event)
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            event.append((curr, i, dp[i]))
            dp[i] = a[curr]

        ans[curr] = len(dp[:bisect_left(dp, INF)])

        seen[curr] = True

        while seen[post_order[post]]:
            c, i, v = event.pop()
            dp[i] = v
            post += 1

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, u, v)


if __name__ == '__main__':
    main()