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: Time Limit Exceeded

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


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()

Submission status: Time Limit Exceeded

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)

    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: Time Limit Exceeded

Solution code:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input


class HeavyLightDecomposition:
    def __init__(self, g, root=0):
        self.g = g
        self.vid, self.head, self.heavy, self.parent = [0] * len(g), [-1] * len(g), [-1] * len(g), [-1] * len(g)
        self.dfs(root)
        self.bfs(root)

    def dfs(self, root):
        stack = [(root, -1, False)]
        sub, max_sub = [1] * len(self.g), [(0, -1)] * len(self.g)
        while stack:
            v, par, flag = stack.pop()
            if not flag:
                self.parent[v] = par
                stack.append((v, par, True))
                stack.extend((c, v, False) for c in self.g[v] if c != par)
            else:
                if par != -1:
                    sub[par] += sub[v]
                    if sub[v] > max_sub[0]:
                        max_sub[par] = (sub[v], v)
                self.heavy[v] = max_sub[v][1]

    def bfs(self, root=0):
        from collections import deque
        k, que = 0, deque([root])
        while que:
            r = v = que.popleft()
            while v != -1:
                self.vid[v], self.head[v] = k, r
                for c in self.g[v]:
                    if c != self.parent[v] and c != self.heavy[v]:
                        que.append(c)
                k += 1
                v = self.heavy[v]

    def lca(self, u, v):
        while self.head[u] != self.head[v]:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
            v = self.parent[self.head[v]]
        else:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
        return u

N = int(input())
g = [[] for _ in range(N)]
for i in range(N):
    for c in map(int, input().split()[1:]):
        g[i].append(c)
        g[c].append(i)
hld = HeavyLightDecomposition(g)
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    print(hld.lca(u, v))

Submission status: Memory 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.descendants = self._dfs()

    def _dfs(self):
        n = self.graph.v
        descendants = [{i} for i 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: Memory Limit Exceeded

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):
        g[i] = list(map(int, readline()[1:].split()))
    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: Accepted

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 = [set() for _ in range(graph.v)]
    for v, w in queries:
        index[v].add((v, w))

    visited = [False] * graph.v
    stored = [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:
            stored[v] = True
            p = parents[v]
            rest = set()
            for i, j in index[v]:
                if stored[i] and stored[j]:
                    if uf.connected(i, j) and (i, j) not in res:
                        res[(i, j)] = v
                    else:
                        rest.add((i, j))
                else:
                    index[j].add((i, j))
            index[v] = None
            if p is not None:
                uf.union(p, v)
                index[p].update(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: Accepted

Solution code:
class Lca:
    def __init__(self, E, root):
        import sys
        sys.setrecursionlimit(500000)
        self.root = root
        self.E = E  # V<V>
        self.n = len(E)  # 頂点数
        self.logn = 1  # n < 1<<logn  ぴったりはだめ
        while self.n >= (1<<self.logn):
            self.logn += 1

        # parent[n][v] = ノード v から 1<<n 個親をたどったノード
        self.parent = [[-1]*self.n for _ in range(self.logn)]

        self.depth = [0] * self.n
        self.dfs(root, -1, 0)
        for k in range(self.logn-1):
            for v in range(self.n):
                p_ = self.parent[k][v]
                if p_ >= 0:
                    self.parent[k+1][v] = self.parent[k][p_]

    def dfs(self, v, p, dep):
        # ノード番号、親のノード番号、深さ
        self.parent[0][v] = p
        self.depth[v] = dep
        for e in self.E[v]:
            if e != p:
                self.dfs(e, v, dep+1)

    def get(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u  # self.depth[u] <= self.depth[v]
        dep_diff = self.depth[v]-self.depth[u]
        for k in range(self.logn):
            if dep_diff >> k & 1:
                v = self.parent[k][v]
        if u==v:
            return u
        for k in range(self.logn-1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

n = int(input())
E = [[] for _ in range(n)]
for i in range(n):
    kc = list(map(int, input().split()))
    k = kc[0]
    for c in kc[1:]:
        E[i].append(c)
        E[c].append(i)
lca = Lca(E, 0)
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    print(lca.get(u, v))

Submission status: Accepted

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:]
    
    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: Accepted

Solution code:
class Edge:
    def __init__(self, dst, weight):
        self.dst, self.weight = dst, weight

    def __lt__(self, e):
        return self.weight > e.weight


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

    def add_edge(self, src, dst, weight):
        self.E[src].append(Edge(dst, weight))


class HeavyLightDecomposition:
    def __init__(self, g, root=0):
        self.g = g
        self.vid, self.head, self.heavy, self.parent = [0] * g.V, [-1] * g.V, [-1] * g.V, [-1] * g.V
        self.dfs(root)
        self.bfs(root)

    def dfs(self, root):
        stack = [(root, -1)]
        sub, max_sub = [1] * self.g.V, [(0, -1)] * self.g.V
        used = [False] * self.g.V

        while stack:
            v, par = stack.pop()
            if not used[v]:
                used[v] = True
                self.parent[v] = par
                stack.append((v, par))
                stack.extend((e.dst, v) for e in self.g.E[v] if e.dst != par)
            else:
                if par != -1:
                    sub[par] += sub[v]
                    max_sub[par] = max(max_sub[par], (sub[v], v))
                self.heavy[v] = max_sub[v][1]

    def bfs(self, root=0):
        from collections import deque
        k, que = 0, deque([root])
        while que:
            r = v = que.popleft()
            while v != -1:
                self.vid[v], self.head[v] = k, r
                for e in self.g.E[v]:
                    if e.dst != self.parent[v] and e.dst != self.heavy[v]:
                        que.append(e.dst)
                k += 1
                v = self.heavy[v]

    def lca(self, u, v):
        while self.head[u] != self.head[v]:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
            v = self.parent[self.head[v]]
        else:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
        return u

N = int(input())
g = Graph(N)
for i in range(N):
    for c in map(int, input().split()[1:]):
        g.add_edge(i, c, 1)
        g.add_edge(c, i, 1)
hld = HeavyLightDecomposition(g)
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    print(hld.lca(u, v))

Submission status: Accepted

Solution code:
class HeavyLightDecomposition:
    def __init__(self, g, root=0):
        self.g = g
        self.vid, self.head, self.heavy, self.parent = [0] * len(g), [-1] * len(g), [-1] * len(g), [-1] * len(g)
        self.dfs(root)
        self.bfs(root)

    def dfs(self, root):
        stack = [(root, -1)]
        sub, max_sub = [1] * len(self.g), [(0, -1)] * len(self.g)
        used = [False] * len(self.g)

        while stack:
            v, par = stack.pop()
            if not used[v]:
                used[v] = True
                self.parent[v] = par
                stack.append((v, par))
                stack.extend((c, v) for c in self.g[v] if c != par)
            else:
                if par != -1:
                    sub[par] += sub[v]
                    max_sub[par] = max(max_sub[par], (sub[v], v))
                self.heavy[v] = max_sub[v][1]

    def bfs(self, root=0):
        from collections import deque
        k, que = 0, deque([root])
        while que:
            r = v = que.popleft()
            while v != -1:
                self.vid[v], self.head[v] = k, r
                for c in self.g[v]:
                    if c != self.parent[v] and c != self.heavy[v]:
                        que.append(c)
                k += 1
                v = self.heavy[v]

    def lca(self, u, v):
        while self.head[u] != self.head[v]:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
            v = self.parent[self.head[v]]
        else:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
        return u

N = int(input())
g = [[] for _ in range(N)]
for i in range(N):
    for c in map(int, input().split()[1:]):
        g[i].append(c)
        g[c].append(i)
hld = HeavyLightDecomposition(g)
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    print(hld.lca(u, v))

Submission status: Accepted

Solution code:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input


class Edge:
    def __init__(self, dst, weight):
        self.dst, self.weight = dst, weight

    def __lt__(self, e):
        return self.weight > e.weight


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

    def add_edge(self, src, dst, weight):
        self.E[src].append(Edge(dst, weight))


class HeavyLightDecomposition:
    def __init__(self, g, root=0):
        self.g = g
        self.vid, self.head, self.heavy, self.parent = [0] * g.V, [-1] * g.V, [-1] * g.V, [-1] * g.V
        self.dfs(root)
        self.bfs(root)

    def dfs(self, root):
        stack = [(root, -1)]
        sub, max_sub = [1] * self.g.V, [(0, -1)] * self.g.V
        used = [False] * self.g.V

        while stack:
            v, par = stack.pop()
            if not used[v]:
                used[v] = True
                self.parent[v] = par
                stack.append((v, par))
                stack.extend((e.dst, v) for e in self.g.E[v] if e.dst != par)
            else:
                if par != -1:
                    sub[par] += sub[v]
                    max_sub[par] = max(max_sub[par], (sub[v], v))
                self.heavy[v] = max_sub[v][1]

    def bfs(self, root=0):
        from collections import deque
        k, que = 0, deque([root])
        while que:
            r = v = que.popleft()
            while v != -1:
                self.vid[v], self.head[v] = k, r
                for e in self.g.E[v]:
                    if e.dst != self.parent[v] and e.dst != self.heavy[v]:
                        que.append(e.dst)
                k += 1
                v = self.heavy[v]

    def lca(self, u, v):
        while self.head[u] != self.head[v]:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
            v = self.parent[self.head[v]]
        else:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
        return u

N = int(input())
g = Graph(N)
for i in range(N):
    for c in map(int, input().split()[1:]):
        g.add_edge(i, c, 1)
        g.add_edge(c, i, 1)
hld = HeavyLightDecomposition(g)
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    print(hld.lca(u, v))

Submission status: Accepted

Solution code:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input

class HeavyLightDecomposition:
    def __init__(self, g, root=0):
        self.g = g
        self.vid, self.head, self.heavy, self.parent = [0] * len(g), [-1] * len(g), [-1] * len(g), [-1] * len(g)
        self.dfs(root)
        self.bfs(root)
 
    def dfs(self, root):
        stack = [(root, -1)]
        sub, max_sub = [1] * len(self.g), [(0, -1)] * len(self.g)
        used = [False] * len(self.g)
 
        while stack:
            v, par = stack.pop()
            if not used[v]:
                used[v] = True
                self.parent[v] = par
                stack.append((v, par))
                stack.extend((c, v) for c in self.g[v] if c != par)
            else:
                if par != -1:
                    sub[par] += sub[v]
                    max_sub[par] = max(max_sub[par], (sub[v], v))
                self.heavy[v] = max_sub[v][1]
 
    def bfs(self, root=0):
        from collections import deque
        k, que = 0, deque([root])
        while que:
            r = v = que.popleft()
            while v != -1:
                self.vid[v], self.head[v] = k, r
                for c in self.g[v]:
                    if c != self.parent[v] and c != self.heavy[v]:
                        que.append(c)
                k += 1
                v = self.heavy[v]
 
    def lca(self, u, v):
        while self.head[u] != self.head[v]:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
            v = self.parent[self.head[v]]
        else:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
        return u
 
N = int(input())
g = [[] for _ in range(N)]
for i in range(N):
    for c in map(int, input().split()[1:]):
        g[i].append(c)
        g[c].append(i)
hld = HeavyLightDecomposition(g)
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    print(hld.lca(u, v))

Submission status: Accepted

Solution code:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input


class Edge:
    def __init__(self, dst, weight):
        self.dst, self.weight = dst, weight

    def __lt__(self, e):
        return self.weight > e.weight


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

    def add_edge(self, src, dst, weight):
        self.E[src].append(Edge(dst, weight))


class HeavyLightDecomposition:
    def __init__(self, g, root=0):
        self.g = g
        self.vid, self.head, self.heavy, self.parent = [0] * g.V, [-1] * g.V, [-1] * g.V, [-1] * g.V
        self.dfs(root)
        self.bfs(root)

    def dfs(self, root):
        stack = [(root, -1, False)]
        sub, max_sub = [1] * self.g.V, [(0, -1)] * self.g.V
        while stack:
            v, par, flag = stack.pop()
            if not flag:
                self.parent[v] = par
                stack.append((v, par, True))
                stack.extend((e.dst, v, False) for e in self.g.E[v] if e.dst != par)
            else:
                if par != -1:
                    sub[par] += sub[v]
                    max_sub[par] = max(max_sub[par], (sub[v], v))
                self.heavy[v] = max_sub[v][1]

    def bfs(self, root=0):
        from collections import deque
        k, que = 0, deque([root])
        while que:
            r = v = que.popleft()
            while v != -1:
                self.vid[v], self.head[v] = k, r
                for e in self.g.E[v]:
                    if e.dst != self.parent[v] and e.dst != self.heavy[v]:
                        que.append(e.dst)
                k += 1
                v = self.heavy[v]

    def lca(self, u, v):
        while self.head[u] != self.head[v]:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
            v = self.parent[self.head[v]]
        else:
            if self.vid[u] > self.vid[v]:
                u, v = v, u
        return u

N = int(input())
g = Graph(N)
for i in range(N):
    for c in map(int, input().split()[1:]):
        g.add_edge(i, c, 1)
        g.add_edge(c, i, 1)
hld = HeavyLightDecomposition(g)
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    print(hld.lca(u, v))