Problem:


LCA: Lowest Common Ancestor

For a rooted tree, find the lowest common ancestor of two nodes u and v.

The given tree consists of n nodes and every node has a unique ID from 0 to n-1 where 0 is the root. 

Input

n
k0 c1 c2 ... ck0
k1 c1 c2 ... ck1
:
kn-1 c1 c2 ... ckn-1
q
u1 v1
u2 v2
:
uq vq

The first line of the input includes an integer n, the number of nodes of the tree.

In the next n lines, the information of node i is given. ki is the number of children of node i, and c1, ... cki are node IDs of 1st, ... kth child of node i. 

In the next line, the number of queryies q is given. In the next q lines, pairs of u and v are given as the queries.

Output

For each query, print the LCA of u and v in a line.

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

Sample Input 1

8
3 1 2 3
2 4 5
0
0
0
2 6 7
0
0
4
4 6
4 7
4 3
5 2

Sample Output 1

1
1
0
0



Sample input:
8
3 1 2 3
2 4 5
0
0
0
2 6 7
0
0
4
4 6
4 7
4 3
5 2


Sample output:
1
1
0
0

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


class LowestCommonAncestor:
    def __init__(self, graph, root):
        self.graph = graph
        self.root = root
        self.descendants = self._dfs()

    def _dfs(self):
        n = self.graph.v
        descendants = [set() for _ in range(n)]
        visited = [False] * n
        edge_to = [None] * n

        stack = [self.root]
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                stack.append(v)
                for e in self.graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        edge_to[w] = v
                        stack.append(w)
            else:
                p = edge_to[v]
                if p is not None:
                    descendants[p].add(v)
                    descendants[p].update(descendants[v])

        return descendants

    def find(self, i, j):
        checked = [False] * self.graph.v
        pair = {i, j}
        v = self.root
        while True:
            checked[v] = True
            for e in self.graph.adj(v):
                w = e.other(v)
                if not checked[w]:
                    if pair <= self.descendants[w]:
                        v = w
                        break
            else:
                return v


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    lca = LowestCommonAncestor(g, 0)
    q = int(input())
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        print(lca.find(v, w))


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor


class UnionFind:
    def __init__(self, n):
        self.nodes = [i for i in range(n)]
        self.sizes = [1 for _ in range(n)]

    def union(self, p, q):
        rp = self.root(p)
        rq = self.root(q)
        if self.sizes[rp] > self.sizes[rq]:
            self.nodes[rq] = rp
            self.sizes[rp] += self.sizes[rq]
        else:
            self.nodes[rp] = rq
            self.sizes[rq] += self.sizes[rp]

    def connected(self, p, q):
        return self.root(p) == self.root(q)

    def root(self, p):
        while p != self.nodes[p]:
            self.nodes[p] = self.nodes[self.nodes[p]]
            p = self.nodes[p]

        return p


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class WeightedEdge(Edge):
    __slots__ = ('v', 'w', 'weight')

    def __init__(self, v, w, weight):
        super().__init__(v, w)
        self.weight = weight


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def lca(graph, root, queries):
    index = [[] for _ in range(graph.v)]
    for v, w in queries:
        index[v].append((v, w))
        index[w].append((v, w))

    visited = [False] * graph.v
    parents = [None] * graph.v
    uf = UnionFind(graph.v)
    res = {}
    stack = [root]
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            stack.append(v)
            for e in graph.adj(v):
                w = e.other(v)
                if not visited[w]:
                    stack.append(w)
                    parents[w] = v
        else:
            p = parents[v]
            rest = []
            for i, j in index[v]:
                if uf.connected(i, j) and (i, j) not in res:
                    res[(i, j)] = v
                else:
                    rest.append((i, j))
            index[v] = None
            if p is not None:
                uf.union(p, v)
                index[p].extend(rest)
            print(p, v, len(res), len(rest))

    return res


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    q = int(input())
    qs = []
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        qs.append((v, w))

    res = lca(g, 0, qs)
    for v, w in qs:
        print(res[(v, w)])


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
readline = stdin.readline
 
 
def main():
    n = int(readline())
    g = dict()
    for i in range(n):
        nodes = list(map(int, readline().split()))
        g[i] = nodes[1:]
    print(g)
    
    euler, height = euler_tour(g, n)
    index = defaultdict(list)
    for i in range(len(euler)):
        index[euler[i]].append(i)
    rmql = [(height[i], i) for i in euler]
    rmq = segment_tree(rmql,min,(float('inf'),))
 
    q = int(readline())
    for i in range(q):
        u, v = map(int, readline().split())
        l, r = index[u][0], index[v][-1]
        if l > r:
            l, r = index[v][0], index[u][-1]
        print(rmq.find(l, r)[1])
 
 
def euler_tour(g, size):
    height = [None] * size
    euler = []
    root = 0
    dfs_stack = [(root, None, 0)]
    while dfs_stack:
        u, prev, h = dfs_stack.pop()
        height[u] = h
        euler.append(prev)
        if g[u]:
            dfs_stack.extend((v, u, h + 1) for v in g[u])
        else:
            euler.append(u)
    return euler[1:], height
     
import math
class segment_tree:
    def __init__(self, dat, query, default=0):
        self.offset = 2 ** math.ceil(math.log(len(dat), 2))
        self.table = [default] * self.offset + dat + [default] * (self.offset - len(dat))
        self.query = query
        for i in reversed(range(1, self.offset)):
            self.table[i] = self.query(self.table[2 * i], self.table[2 * i + 1])
 
    # [l, r] closed-interval
    def find(self, l, r):
        return self.query(self.__range(l,r))
 
    def __range(self, l, r):
        l += self.offset
        r += self.offset
        while l <= r:
            if l & 1:
                yield self.table[l]
                l += 1
            l >>= 1
            if r & 1 == 0:
                yield self.table[r]
                r -= 1
            r >>= 1
         
    def update(self, i, x):
        i += self.offset
        self.table[i] = x
        while 1 < i:
            i >>= 1
            self.table[i] = self.query(self.table[2 * i], self.table[2 * i + 1])
main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
8
3 1 2 3
2 4 5
0
0
0
2 6 7
0
0
4
4 6
4 7
4 3
5 2

output:
1
1
0
0
"""

import sys

sys.setrecursionlimit(int(1e5))


class UnionFind(object):
    __slots__ = ('size', 'height_rank', 'ancestors')

    def __init__(self, size):
        self.size = int(size)
        self.height_rank = [0] * self.size
        self.ancestors = [i for i in range(self.size)]

    def find(self, x):
        if x != self.ancestors[x]:
            self.ancestors[x] = self.find(self.ancestors[x])
        return self.ancestors[x]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def __link(self, x, y):
        if self.height_rank[x] > self.height_rank[y]:
            self.ancestors[y] = x
        else:
            self.ancestors[x] = y
            if self.height_rank[x] == self.height_rank[y]:
                self.height_rank[y] += 1

    def union(self, x, y):
        self.__link(self.find(x), self.find(y))


def graph_Tarjan(current, uf, adj_table, g_ancestors, vs, queries_table):
    for adj in adj_table[current]:
        graph_Tarjan(adj, uf, adj_table, g_ancestors, vs, queries_table)
        uf.union(current, adj)
        g_ancestors[uf.find(current)] = current

    vs[current] = True

    for v in queries_table[current]:
        if vs[v]:
            print(g_ancestors[uf.find(v)])

    return None


def cmd_exec(queries, v_num, c_edges):
    # get adj_table
    adj_table = tuple([] for _ in range(v_num))
    queries_table = tuple([] for _ in range(v_num))
    g_ancestors = [i for i in range(v_num)]
    vs = [False] * v_num

    for parent, edge in enumerate(c_edges):
        c_num, *children = map(int, edge)
        assert len(children) == c_num
        adj_table[parent].extend(children)

    for query in queries:
        q1, q2 = map(int, query)
        queries_table[q1].append(q2)
        queries_table[q2].append(q1)

    root = 0
    uf = UnionFind(size=v_num)
    graph_Tarjan(root, uf, adj_table, g_ancestors, vs, queries_table)

    return None


def solve():
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    c_edges = map(lambda x: x.split(), _input[1:v_num + 1])
    q_num = int(_input[v_num + 1])
    c_queries = map(lambda x: x.split(), _input[v_num + 2:])
    cmd_exec(queries=c_queries, v_num=v_num, c_edges=c_edges)

    return None


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
8
3 1 2 3
2 4 5
0
0
0
2 6 7
0
0
4
4 6
4 7
4 3
5 2

output:
1
1
0
0
"""

import sys
import math


def rmq_init(node, begin, end):
    if begin == end:
        M[node] = begin
    else:
        rmq_init(2 * node, begin, (begin + end) // 2)
        rmq_init(2 * node + 1, (begin + end) // 2 + 1, end)
        if depth[M[2 * node]] <= depth[M[2 * node + 1]]:
            M[node] = M[2 * node]
        else:
            M[node] = M[2 * node + 1]

    return M


def rmq_query(node, begin, end, s, t):
    if s > end or t < begin:
        return -1
    if begin >= s and end <= t:
        return M[node]

    p1 = rmq_query(2 * node, begin, (begin + end) // 2, s, t)
    p2 = rmq_query(2 * node + 1, (begin + end) // 2 + 1, end, s, t)

    if p1 == -1:
        M[node] = p2
        return p2
    if p2 == -1:
        M[node] = p1
        return p1

    if depth[p1] <= depth[p2]:
        M[node] = p1
        return p1

    M[node] = p2
    return p2


def dfs(current, parent, c_depth):
    global timer
    ids[current] = timer
    vs[timer] = current
    depth[timer] = c_depth
    timer += 1

    for adj in adj_table[current]:
        if adj != parent:
            dfs(adj, current, c_depth + 1)
            vs[timer] = current
            depth[timer] = c_depth
            timer += 1

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    c_edges = map(lambda x: x.split(), _input[1:v_num + 1])
    q_num = int(_input[v_num + 1])
    c_queries = map(lambda x: x.split(), _input[v_num + 2:])

    adj_table = tuple([] for _ in range(v_num))
    for idx, edge in enumerate(c_edges):
        c_num, *children = map(int, edge)
        # assert len(children) == c_num
        adj_table[idx].extend(children)

    ext_length = 2 * v_num - 1
    vs, depth = ([-1] * ext_length for _ in range(2))
    ids = [-1] * v_num

    root = 0
    timer = 0
    dfs(root, -1, 0)
    M = [-1] * (pow(2, math.ceil(math.log2(ext_length)) + 1) + 1)
    # print(vs, depth, ids)

    rmq_init(node=1, begin=0, end=ext_length - 1)
    for query in c_queries:
        q1, q2 = map(int, query)
        q_min = min(ids[q1], ids[q2])
        q_max = max(ids[q1], ids[q2])
        vs_idx = rmq_query(node=1, begin=0, end=ext_length - 1, s=q_min, t=q_max)
        print(vs[vs_idx])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


"""
input:
16
3 1 2 3
3 4 5 6
0
2 7 8
0
2 9 10
2 14 15
0
0
0
3 11 12 13
0
0
0
0
0
10
1 3
4 5
4 9
4 10
4 13
9 13
9 14
9 8
13 14
13 7

output:
0
1
1
1
1
5
1
0
1
0
"""

import sys
import math

sys.setrecursionlimit(int(1e5))


def dfs(v, v_parent, v_depth):
    # print(parent, v, v_parent)
    if not parent:
        return 0
    parent[0][v] = v_parent
    depth[v] = v_depth
    for adj in adj_table[v]:
        if adj != v_parent:
            dfs(adj, v, v_depth + 1)

    return None


def dfs_init():
    dfs(root, -1, 0)
    for k in range(v_log - 1):
        for v in range(v_num):
            if parent[k][v] < 0:
                parent[k + 1][v] = -1
            else:
                parent[k + 1][v] = parent[k][parent[k][v]]

    return None


def lca(u, v):
    if depth[u] > depth[v]:
        u, v = v, u
    for k in range(v_log):
        if (depth[v] - depth[u]) >> k & 1:
            v = parent[k][v]

    if u == v:
        return u

    for k in range(v_log - 1, -1, -1):
        if parent[k][u] != parent[k][v]:
            u = parent[k][u]
            v = parent[k][v]

    return parent[0][u]


def cmd_exec():
    for query in c_queries:
        q1, q2 = map(int, query)
        print(lca(q1, q2))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    c_edges = map(lambda x: x.split(), _input[1:v_num + 1])
    q_num = int(_input[v_num + 1])
    c_queries = map(lambda x: x.split(), _input[v_num + 2:])

    v_log = math.floor(math.log2(v_num))
    parent = [[-1] * v_num for _ in range(v_log)]
    depth = [-1] * v_num
    root = 0

    adj_table = tuple([] for _ in range(v_num))
    for idx, edge in enumerate(c_edges):
        c_num, *children = map(int, edge)
        # assert len(children) == c_num
        adj_table[idx].extend(children)

    dfs_init()
    cmd_exec()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


"""
input:
16
3 1 2 3
3 4 5 6
0
2 7 8
0
2 9 10
2 14 15
0
0
0
3 11 12 13
0
0
0
0
0
10
1 3
4 5
4 9
4 10
4 13
9 13
9 14
9 8
13 14
13 7

output:
0
1
1
1
1
5
1
0
1
0
"""

import sys
import math

sys.setrecursionlimit(int(1e6))


def dfs(v, v_parent, v_depth):
    # print(parent, v, v_parent)
    if not parent:
        return 0
    parent[0][v] = v_parent
    depth[v] = v_depth
    for adj in adj_table[v]:
        if adj != v_parent:
            dfs(adj, v, v_depth + 1)

    return None


def dfs_init():
    dfs(root, -1, 0)
    for k in range(v_log - 1):
        for v in range(v_num):
            if parent[k][v] < 0:
                parent[k + 1][v] = -1
            else:
                parent[k + 1][v] = parent[k][parent[k][v]]

    return None


def lca(u, v):
    if depth[u] > depth[v]:
        u, v = v, u
    for k in range(v_log):
        if (depth[v] - depth[u]) >> k & 1:
            v = parent[k][v]

    if u == v:
        return u

    for k in range(v_log - 1, -1, -1):
        if parent[k][u] != parent[k][v]:
            u = parent[k][u]
            v = parent[k][v]

    return parent[0][u]


def cmd_exec():
    for query in c_queries:
        q1, q2 = map(int, query)
        print(lca(q1, q2))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    c_edges = map(lambda x: x.split(), _input[1:v_num + 1])
    q_num = int(_input[v_num + 1])
    c_queries = map(lambda x: x.split(), _input[v_num + 2:])

    v_log = math.floor(math.log2(v_num))
    parent = [[-1] * v_num for _ in range(v_log)]
    depth = [-1] * v_num
    root = 0

    adj_table = tuple([] for _ in range(v_num))
    for idx, edge in enumerate(c_edges):
        c_num, *children = map(int, edge)
        # assert len(children) == c_num
        adj_table[idx].extend(children)

    dfs_init()
    cmd_exec()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


"""
input:
16
3 1 2 3
3 4 5 6
0
2 7 8
0
2 9 10
2 14 15
0
0
0
3 11 12 13
0
0
0
0
0
10
1 3
4 5
4 9
4 10
4 13
9 13
9 14
9 8
13 14
13 7

output:
0
1
1
1
1
5
1
0
1
0
"""

import sys
import math

sys.setrecursionlimit(int(1e6))


def dfs(v, v_parent, v_depth):
    # print(parent, v, v_parent)
    if not parent:
        return v_parent
    parent[0][v] = v_parent
    depth[v] = v_depth
    for adj in adj_table[v]:
        if adj != v_parent:
            dfs(adj, v, v_depth + 1)

    return None


def dfs_init():
    dfs(root, -1, 0)
    for k in range(v_log - 1):
        for v in range(v_num):
            if parent[k][v] < 0:
                parent[k + 1][v] = -1
            else:
                parent[k + 1][v] = parent[k][parent[k][v]]

    return None


def lca(u, v):
    if depth[u] > depth[v]:
        u, v = v, u
    for k in range(v_log):
        if (depth[v] - depth[u]) >> k & 1:
            v = parent[k][v]

    if u == v:
        return u

    for k in range(v_log - 1, -1, -1):
        if parent[k][u] != parent[k][v]:
            u = parent[k][u]
            v = parent[k][v]

    return parent[0][u]


def cmd_exec():
    for query in c_queries:
        q1, q2 = map(int, query)
        print(lca(q1, q2))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    c_edges = map(lambda x: x.split(), _input[1:v_num + 1])
    q_num = int(_input[v_num + 1])
    c_queries = map(lambda x: x.split(), _input[v_num + 2:])

    v_log = math.floor(math.log2(v_num))
    parent = [[-1] * v_num for _ in range(v_log)]
    depth = [-1] * v_num
    root = 0

    adj_table = tuple([] for _ in range(v_num))
    for idx, edge in enumerate(c_edges):
        c_num, *children = map(int, edge)
        # assert len(children) == c_num
        adj_table[idx].extend(children)

    dfs_init()
    cmd_exec()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


"""
input:
16
3 1 2 3
3 4 5 6
0
2 7 8
0
2 9 10
2 14 15
0
0
0
3 11 12 13
0
0
0
0
0
10
1 3
4 5
4 9
4 10
4 13
9 13
9 14
9 8
13 14
13 7

output:
0
1
1
1
1
5
1
0
1
0
"""

import sys
import math

sys.setrecursionlimit(int(1e5))


def dfs(v, v_parent, v_depth):
    # print(parent, v, v_parent)
    if not parent:
        return v_parent
    parent[0][v] = v_parent
    depth[v] = v_depth
    for adj in adj_table[v]:
        if adj != v_parent:
            dfs(adj, v, v_depth + 1)

    return None


def dfs_init():
    dfs(root, -1, 0)
    for k in range(v_log - 1):
        for v in range(v_num):
            if parent[k][v] < 0:
                parent[k + 1][v] = -1
            else:
                parent[k + 1][v] = parent[k][parent[k][v]]

    return None


def lca(u, v):
    if depth[u] > depth[v]:
        u, v = v, u
    for k in range(v_log):
        if ((depth[v] - depth[u]) >> k) % 2 == 1:
            v = parent[k][v]

    if u == v:
        return u

    for k in range(v_log - 1, -1, -1):
        if parent[k][u] != parent[k][v]:
            u = parent[k][u]
            v = parent[k][v]

    return parent[0][u]


def cmd_exec():
    for query in c_queries:
        q1, q2 = map(int, query)
        print(lca(q1, q2))

    return None


if __name__ == '__main__':
    # with open('test.txt', 'r') as f:
    #     _input = f.readlines()
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    c_edges = map(lambda x: x.split(), _input[1:v_num + 1])
    q_num = int(_input[v_num + 1])
    c_queries = map(lambda x: x.split(), _input[v_num + 2:])

    v_log = math.floor(math.log2(v_num))
    parent = [[-1] * v_num for _ in range(v_log)]
    depth = [-1] * v_num
    root = 0

    adj_table = tuple([] for _ in range(v_num))
    for idx, edge in enumerate(c_edges):
        c_num, *children = map(int, edge)
        # assert len(children) == c_num
        adj_table[idx].extend(children)

    dfs_init()
    cmd_exec()

Submission status: Wrong Answer

Solution code:
from math import log2


def build():
    dfs()
    pk0 = parent[0]
    for pk1 in parent[1:]:
        for v in range(n):
            pkv = pk0[v]
            pk1[v] = -1 if pkv < 0 else pk0[pkv]
        pk0 = pk1


def dfs():
    stack = [(0, -1, 0)]
    while stack:
        v, p, d = stack.pop()
        parent[0][v] = p
        depth[v] = d
        stack.extend((child, v, d + 1) for child in tree[v])


def get(u, v):
    du, dv = depth[u], depth[v]
    if du > dv:
        u, v = v, u
        du, dv = dv, du
    for k, pk in enumerate(parent):
        if (dv - du) >> k & 1:
            v = pk[v]
    if u == v:
        return u
    for pk in parent[logn - 1:-1:-1]:
        pku, pkv = pk[u], pk[v]
        if pku != pkv:
            u, v = pku, pkv
    return parent[0][u]


n = int(input())
tree = [set(map(int, input().split()[1:])) for _ in range(n)]

logn = int(log2(n)) + 1
parent = [[0] * n for _ in range(logn)]
depth = [0] * n
build()

q = int(input())
for _ in range(q):
    print(get(*map(int, input().split())))

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

def dfs(here, p, d, parent, depth, connect):
    parent[0][here] = p
    depth[here] = d
    for next_v in connect[here]:
        dfs(next_v, here, d + 1, parent, depth, connect)

def lca(v1, v2, parent):
    v1, v2 = max(v1, v2), min(v1, v2)
    for i in range(max_log):
        if depth[v1] - depth[v2] >> i & 1:
            v1 = parent[i][v1]
    if v1 == v2:
        return v2
    for i in range(max_log - 1, -1, -1):
        if parent[i][v1] != parent[i][v2]:
            v1 = parent[i][v1]
            v2 = parent[i][v2]
    return parent[0][v2]

connect = defaultdict(list)
v_num = int(input())
root = 0
for i in range(v_num):
    edge = [int(n) for n in input().split(" ")]
    connect[i].extend(edge[1:])
depth = [-1 for n in range(v_num)]
max_log = int(math.log(v_num, 2))
parent = [[-1 for n in range(v_num)] for m in range(max_log)]
dfs(root, -1, 0, parent, depth, connect)
for i in range(max_log - 1):
    for v in range(v_num):
        parent[i + 1][v] = -1 if parent[i][v] < 0 else parent[i][parent[i][v]]
q_num = int(input())
for _ in range(q_num):
    v1, v2 = (int(n) for n in input().split(" ") )
    print(lca(v1, v2, parent))

Submission status: Wrong Answer

Solution code:
import math
import sys
from collections import defaultdict
sys.setrecursionlimit(200000)

def dfs(here, p, d, parent, depth, connect):
    parent[0][here] = p
    depth[here] = d
    for next_v in connect[here]:
        dfs(next_v, here, d + 1, parent, depth, connect)

def lca(v1, v2, parent, depth):
    if depth[v2] > depth[v1]:
        v1, v2 = v2, v1
    for i in range(max_log):
        if depth[v1] - depth[v2] >> i & 1:
            v1 = parent[i][v1]
    if v1 == v2:
        return v2
    for i in range(max_log - 1, -1, -1):
        if parent[i][v1] != parent[i][v2]:
            v1 = parent[i][v1]
            v2 = parent[i][v2]
    return parent[0][v2]

connect = defaultdict(list)
v_num = int(input())
root = 0
for i in range(v_num):
    edge = [int(n) for n in input().split(" ")]
    connect[i].extend(edge[1:])
depth = [-1 for n in range(v_num)]
max_log = max(int(math.log(v_num, 2)), 1)
parent = [[-1 for n in range(v_num)] for m in range(max_log)]
dfs(root, -1, 0, parent, depth, connect)
for i in range(max_log - 1):
    for v in range(v_num):
        parent[i + 1][v] = -1 if parent[i][v] < 0 else parent[i][parent[i][v]]
q_num = int(input())
for _ in range(q_num):
    v1, v2 = (int(n) for n in input().split(" ") )
    print(lca(v1, v2, parent, depth))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


class LowestCommonAncestor:
    def __init__(self, graph, root):
        self.graph = graph
        self.root = root
        self._dfs()

    def _dfs(self):
        n = self.graph.v
        visited = [False] * n
        parent = [None] * n
        post_order = [0] * n

        stack = [self.root]
        i = 0
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                stack.append(v)
                for e in self.graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        parent[w] = v
                        stack.append(w)
            else:
                post_order[v] = i
                i += 1

        self.post_order = post_order
        self.parent = parent

    def find(self, v, w):
        ps = self.parent
        pos = self.post_order
        i = pos[v]
        j = pos[w]
        if i > j:
            i, j = j, i
            v, w = w, v

        while i < j and v != self.root:
            v = ps[v]
            i = pos[v]
        return v


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    lca = LowestCommonAncestor(g, 0)
    q = int(input())
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        print(lca.find(v, w))


if __name__ == '__main__':
    run()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor
# Post Order順を使用して判定する
# q = 100000では3分近くかかり、実用に耐えず


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


class LowestCommonAncestor:
    def __init__(self, graph, root):
        self.graph = graph
        self.root = root
        self._cache = {}
        self._dfs()

    def _dfs(self):
        n = self.graph.v
        visited = [False] * n
        parent = [None] * n
        post_order = [0] * n

        stack = [self.root]
        i = 0
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                stack.append(v)
                for e in self.graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        parent[w] = v
                        stack.append(w)
            else:
                post_order[v] = i
                i += 1

        self.post_order = post_order
        self.parent = parent

    def find(self, v, w):
        pos = self.post_order
        i = pos[v]
        j = pos[w]
        if i > j:
            i, j = j, i
            v, w = w, v

        vv = v
        while i < j:
            if (vv, w) in self._cache:
                vv = self._cache[(vv, w)]
                break
            vv = self.parent[vv]
            i = pos[vv]

        self._cache[(v, w)] = vv
        return vv


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    lca = LowestCommonAncestor(g, 0)
    q = int(input())
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        print(lca.find(v, w))


if __name__ == '__main__':
    run()