Problem p02834 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


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

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


INF = float("inf")


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    g = Graph(N)
    for a, b in zip(A, B):
        g.add_edge(a-1, b-1)

    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    ffhouse = [0]*N

    def dfs(f_, pre, dep):
        ffhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(u-1, -1, 0)
    m = 0
    for d, f in zip(ddhouse, ffhouse):
        if f >= d:
            continue
        else:
            m = max(d, m)
    print(max(m-1, 0))
    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
    u = int(next(tokens))  # type: int
    v = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, u, v, A, B)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


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

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


INF = float("inf")


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    g = Graph(N)
    for a, b in zip(A, B):
        g.add_edge(a-1, b-1)

    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    ffhouse = [0]*N

    def dfs(f_, pre, dep):
        ffhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(u-1, -1, 0)
    m = 0
    for d, f in zip(ddhouse, ffhouse):
        if f >= d:
            continue
        else:
            m = max(d, m)
    print(max(m-1, 0))
    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
    u = int(next(tokens))  # type: int
    v = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, u, v, A, B)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


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

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


INF = float("inf")


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    g = Graph(N)
    for a, b in zip(A, B):
        g.add_edge(a-1, b-1)

    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    ffhouse = [0]*N

    def dfs(f_, pre, dep):
        ffhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(u-1, -1, 0)
    m = 0
    for d, f in zip(ddhouse, ffhouse):
        if f >= d:
            continue
        else:
            m = max(d, m)
    print(max(m-1, 0))
    print(ddhouse, ffhouse)
    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
    u = int(next(tokens))  # type: int
    v = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, u, v, A, B)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


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

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


INF = float("inf")


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    g = Graph(N)
    for a, b in zip(A, B):
        g.add_edge(a-1, b-1)

    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    ffhouse = [0]*N

    def dfs(f_, pre, dep):
        ffhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(u-1, -1, 0)
    m = 0
    for d, f in zip(ddhouse, ffhouse):
        if f >= d:
            continue
        else:
            m = max(d, m)
    print(max(m-1, 0))
    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
    u = int(next(tokens))  # type: int
    v = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, u, v, A, B)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


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

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


def LCA_constract(g: Graph, root=0):
    N = g.N
    LN = int(math.log2(g.N))

    ###
    # 各頂点の親 parと各頂点の深さdepthを求める
    ###
    par = [INF]*N
    depth = [INF]*N

    que = deque()
    que.append([root, 0, None])
    while len(que) > 0:
        curr, dep, pre = que.popleft()
        par[curr] = pre
        depth[curr] = dep
        for n, w in g.E[curr]:
            if n != pre:
                que.append([n, dep+w, curr])

    ###
    # 祖先 ancの構築
    ###

    anc = [par]

    for i in range(LN):
        buf = [None]*N
        for j in range(N):
            if anc[i][j] == None:
                continue
            buf[j] = anc[i][anc[i][j]]
        anc.append(buf)
    return anc, depth


def LCA_query(anc, depth, g, u: int, v: int):
    N = len(depth)
    LN = int(math.log2(g.N))

    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    # assert depth[u] <= depth[v]
    for k in range(LN):
        if dd & 1:
            v = anc[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LN-1, -1, -1):
        pu = anc[k][u]
        pv = anc[k][v]
        if pu != pv:
            u = pu
            v = pv

    # assert anc[0][u] == anc[0][v]
    return anc[0][u]


INF = float("inf")


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    g = Graph(N)
    for a, b in zip(A, B):
        g.add_edge(a-1, b-1)

    anc, depth = LCA_constract(g, v-1)

    visited = [False] * N
    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        visited[f_] = True
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre or visited[t_] == True:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    visited = [False] * N
    ffhouse = [0]*N

    def dfs(f_, pre, dep):
        visited[f_] = True
        ffhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre or visited[t_] == True:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(u-1, -1, 0)
    m = 0

    for d, f in zip(ddhouse, ffhouse):
        if f >= d:
            continue
        else:
            m = max(d, m)
    print(max(m-1, 0))

    # while True:
    #     # 最も深いノード
    #     if current == N:
    #         print(0)
    #         return
    #     dep, node = ffhouse[current]
    #     lca = LCA_query(anc, ffhouse, g, node, u-1)
    #     # print("最も深いノード: ", node)
    #     # print("LCA ({}, {}) => {}".format(u-1, node, lca))

    #     # 到達可能か
    #     if (ddhouse[u-1] - dep) < dep:
    #         # 到達可能。移動すべし。
    #         # print("到達可能")
    #         break
    #     else:
    #         current += 1
    #         continue
    # print(dep-1)
    # 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
    u = int(next(tokens))  # type: int
    v = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, u, v, A, B)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


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

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


def LCA_constract(g: Graph, root=0):
    N = g.N
    LN = int(math.log2(g.N))

    ###
    # 各頂点の親 parと各頂点の深さdepthを求める
    ###
    par = [INF]*N
    depth = [INF]*N

    que = deque()
    que.append([root, 0, None])
    while len(que) > 0:
        curr, dep, pre = que.popleft()
        par[curr] = pre
        depth[curr] = dep
        for n, w in g.E[curr]:
            if n != pre:
                que.append([n, dep+w, curr])

    ###
    # 祖先 ancの構築
    ###

    anc = [par]

    for i in range(LN):
        buf = [None]*N
        for j in range(N):
            if anc[i][j] == None:
                continue
            buf[j] = anc[i][anc[i][j]]
        anc.append(buf)
    return anc, depth


def LCA_query(anc, depth, g, u: int, v: int):
    N = len(depth)
    LN = int(math.log2(g.N))

    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    # assert depth[u] <= depth[v]
    for k in range(LN):
        if dd & 1:
            v = anc[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LN-1, -1, -1):
        pu = anc[k][u]
        pv = anc[k][v]
        if pu != pv:
            u = pu
            v = pv

    # assert anc[0][u] == anc[0][v]
    return anc[0][u]


INF = float("inf")


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    g = Graph(N)
    for a, b in zip(A, B):
        g.add_edge(a-1, b-1)

    anc, depth = LCA_constract(g, v-1)

    visited = [False] * N
    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        visited[f_] = True
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre or visited[t_] == True:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    ffhouse = sorted(zip(ddhouse, range(N)), reverse=True)
    current = 0
    # print(ffhouse)

    while True:
        # 最も深いノード
        if current == N:
            print(0)
            return
        dep, node = ffhouse[current]
        lca = LCA_query(anc, ddhouse, g, node, u-1)
        # print("最も深いノード: ", node)
        # print("LCA ({}, {}) => {}".format(u-1, node, lca))

        # 到達可能か
        if (ddhouse[u-1] - dep) < dep:
            # 到達可能。移動すべし。
            # print("到達可能")
            break
        else:
            current += 1
            continue
    print(dep-1)
    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
    u = int(next(tokens))  # type: int
    v = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, u, v, A, B)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


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

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


def LCA_constract(g: Graph, root=0):
    N = g.N
    LN = int(math.log2(g.N))

    ###
    # 各頂点の親 parと各頂点の深さdepthを求める
    ###
    par = [INF]*N
    depth = [INF]*N

    que = deque()
    que.append([root, 0, None])
    while len(que) > 0:
        curr, dep, pre = que.popleft()
        par[curr] = pre
        depth[curr] = dep
        for n, w in g.E[curr]:
            if n != pre:
                que.append([n, dep+w, curr])

    ###
    # 祖先 ancの構築
    ###

    anc = [par]

    for i in range(LN):
        buf = [None]*N
        for j in range(N):
            if anc[i][j] == None:
                continue
            buf[j] = anc[i][anc[i][j]]
        anc.append(buf)
    return anc, depth


def LCA_query(anc, depth, g, u: int, v: int):
    N = len(depth)
    LN = int(math.log2(g.N))

    dd = depth[v] - depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd

    # assert depth[u] <= depth[v]
    for k in range(LN):
        if dd & 1:
            v = anc[k][v]
        dd >>= 1

    # assert depth[u] == depth[v]
    if u == v:
        return u

    for k in range(LN-1, -1, -1):
        pu = anc[k][u]
        pv = anc[k][v]
        if pu != pv:
            u = pu
            v = pv

    # assert anc[0][u] == anc[0][v]
    return anc[0][u]


INF = float("inf")


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    g = Graph(N)
    for a, b in zip(A, B):
        g.add_edge(a-1, b-1)

    anc, depth = LCA_constract(g, v-1)

    visited = [False] * N
    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        visited[f_] = True
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre or visited[t_] == True:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    ffhouse = sorted(zip(ddhouse, range(N)), reverse=True)
    current = 0
    # print(ffhouse)

    while True:
        # 最も深いノード
        dep, node = ffhouse[current]
        lca = LCA_query(anc, ddhouse, g, node, u-1)
        # print("最も深いノード: ", node)
        # print("LCA ({}, {}) => {}".format(u-1, node, lca))

        # 到達可能か
        if (ddhouse[u-1] - dep) < dep:
            # 到達可能。移動すべし。
            # print("到達可能")
            break
        else:
            current += 1
            continue
    print(dep-1)
    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
    u = int(next(tokens))  # type: int
    v = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, u, v, A, B)


if __name__ == '__main__':
    main()