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

Solution code:
from math import log2
import time
import sys

MOD = 10 ** 9 + 7

def lca(u, v):
    if level[u] < level[v]: u, v = v, u

    up = int(log2(level[u]))
    while up >= 0:
    	if level[u] - (1 << up) >= level[v]:
    		u = par[u][up]
    	up -= 1

    if u == v: return v

    up = int(log2(level[u]))
    while up >= 0:
    	if par[u][up] and par[v][up] != par[u][up]:
    		u, v = par[u][up], par[v][up]
    	up -= 1

    return par[u][0]

n = int(input())

adj = {}
u = 0
for _ in range(n):
    c, *v_list = [int(item) for item in sys.stdin.readline().strip().split()]
    adj[u] = []
    for v in v_list:
        adj[u].append(v)
    u += 1

start = 0

Q = [start]
done = [0] * (n + 1)
par = [[0] * (int(log2(n)) + 1) for _ in range(n + 1)]
level = [0] * (n + 1)
level[start] = 1

while Q:
    current = Q.pop()
    for nxt in adj[current]:
        if done[nxt]: continue
        done[current] = 1
        level[nxt] = level[current] + 1
        par[nxt][0] = current
        Q.append(nxt)

lvl = 1
while (1 << lvl) < n:
	for i in range(0, n):
		if par[i][lvl - 1]: par[i][lvl] = par[par[i][lvl - 1]][lvl - 1]
	lvl += 1

q = int(input())
for _ in range(q):
	u, v = [int(item) for item in sys.stdin.readline().strip().split()]
	_lca = lca(u, v)
	print(_lca)

Submission status: Runtime Error

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 = 0
        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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from math import log

def dfs(v,p,d):
    parent[0][v]=p
    depth[v]=d
    for i in xrange(len(G[v])):
        if G[v][i]!=p:
            dfs(G[v][i],v,d+1)

def init(vn,root):
    dfs(root,-1,0)
    k=0
    while k+1<log(vn,2):
        for v in xrange(vn):
            if parent[k][v]<0:
                parent[k+1][v]=-1
            else:
                parent[k+1][v]=parent[k][parent[k][v]]
        k+=1

def lca(u,v,vn):
    if depth[u]>depth[v]:u,v=v,u
    k=0
    while k<log(vn,2):
        if (depth[v]-depth[u])>>k&1:
            v=parent[k][v]
        k+=1
    if u==v:return u
    for k in xrange(int(log(vn,2))-1,-1,-1):
        if parent[k][u]!=parent[k][v]:
            u=parent[k][u]
            v=parent[k][v]
    return parent[0][u]


vn=int(raw_input())        #????????°
G=[[] for _ in xrange(vn)] #??£??\?????????
parent=[[-1]*vn for _ in xrange(int(log(vn,2))+1)] #parent[k][u]:??????u??????2^k????????????????????£?????¨????????????
depth=[0]*vn               #depth[u]:??????u?????????????????±??????????????±??????0
root=0                     #??????????????????

for i in xrange(vn):
    en=map(int,raw_input().split())
    c=en[1:]          #????????????i??????
    G[i]=c

init(vn,root)

q=int(raw_input())
for _ in xrange(q):
    u,v=map(int,raw_input().split())
    print(lca(u,v,vn))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from math import log
import sys
sys.setrecursionlimit(10**7)

def dfs(v,p,d):
    parent[0][v]=p
    depth[v]=d
    for i in xrange(len(G[v])):
        if G[v][i]!=p:
            dfs(G[v][i],v,d+1)

def init(vn,root):
    dfs(root,-1,0)
    k=0
    while k+1<log(vn,2):
        for v in xrange(vn):
            if parent[k][v]<0:
                parent[k+1][v]=-1
            else:
                parent[k+1][v]=parent[k][parent[k][v]]
        k+=1

def lca(u,v,vn):
    if depth[u]>depth[v]:u,v=v,u
    k=0
    while k<log(vn,2):
        if (depth[v]-depth[u])>>k&1:
            v=parent[k][v]
        k+=1
    if u==v:return u
    for k in xrange(int(log(vn,2))-1,-1,-1):
        if parent[k][u]!=parent[k][v]:
            u=parent[k][u]
            v=parent[k][v]
    return parent[0][u]


vn=int(raw_input())        #????????°
G=[[] for _ in xrange(vn)] #??£??\?????????
parent=[[-1]*vn for _ in xrange(int(log(vn,2))+1)] #parent[k][u]:??????u??????2^k????????????????????£?????¨????????????
depth=[0]*vn               #depth[u]:??????u?????????????????±??????????????±??????0
root=0                     #??????????????????

for i in xrange(vn):
    en=map(int,raw_input().split())
    c=en[1:]          #????????????i??????
    G[i]=c

init(vn,root)

q=int(raw_input())
for _ in xrange(q):
    u,v=map(int,raw_input().split())
    print(lca(u,v,vn))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from math import log
import sys
sys.setrecursionlimit(10**9)

def dfs(v,p,d):
    parent[0][v]=p
    depth[v]=d
    for i in xrange(len(G[v])):
        if G[v][i]!=p:
            dfs(G[v][i],v,d+1)

def init(vn,root):
    dfs(root,-1,0)
    k=0
    while k+1<log(vn,2):
        for v in xrange(vn):
            if parent[k][v]<0:
                parent[k+1][v]=-1
            else:
                parent[k+1][v]=parent[k][parent[k][v]]
        k+=1

def lca(u,v,vn):
    if depth[u]>depth[v]:u,v=v,u
    k=0
    while k<log(vn,2):
        if (depth[v]-depth[u])>>k&1:
            v=parent[k][v]
        k+=1
    if u==v:return u
    for k in xrange(int(log(vn,2))-1,-1,-1):
        if parent[k][u]!=parent[k][v]:
            u=parent[k][u]
            v=parent[k][v]
    return parent[0][u]


vn=int(raw_input())        #????????°
G=[[] for _ in xrange(vn)] #??£??\?????????
parent=[[-1]*vn for _ in xrange(int(log(vn,2))+1)] #parent[k][u]:??????u??????2^k????????????????????£?????¨????????????
depth=[0]*vn               #depth[u]:??????u?????????????????±??????????????±??????0
root=0                     #??????????????????

for i in xrange(vn):
    en=map(int,raw_input().split())
    c=en[1:]          #????????????i??????
    G[i]=c

init(vn,root)

q=int(raw_input())
for _ in xrange(q):
    u,v=map(int,raw_input().split())
    print(lca(u,v,vn))

Submission status: Runtime Error

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


def dfs(v, v_parent, v_depth):
    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: Runtime Error

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):
    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: Runtime Error

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)
    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__':
    # 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: Runtime Error

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)
    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__':
    # 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)) + 1
    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: Runtime Error

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

"""
input:
3
0.0 0.0
2.0 0.0
1.0 1.0

output:
1.41421356237
"""

import sys
from operator import attrgetter


class ClosestPair(object):
    def __init__(self, in_data):
        """
        Init closest pairs points set.
        """
        self.p_num = int(in_data[0])
        points = map(lambda x: x.split(), in_data[1:])
        p_list = [complex(float(x), float(y)) for x, y in points]
        # pre_sort by axis_X
        self.p_list = sorted(p_list, key=attrgetter('real'))

    def closest_pair(self, array, array_length):
        if array_length <= 1:
            return float('inf')
        mid_idx = array_length // 2
        div_line = array[mid_idx].real
        d_min = min(self.closest_pair(array[:mid_idx], mid_idx),
                    self.closest_pair(array[mid_idx:], array_length - mid_idx))

        # sort array_part by axis_Y while recursively comparing
        array.sort(key=attrgetter('imag'))

        min_stack = list()
        for ele in array:
            size = len(min_stack)

            # eliminate p which distance(p,div_line) >= d
            if abs(ele.real - div_line) >= d_min:
                continue

            for j in range(size):
                alt = ele - min_stack[size - j - 1]
                if alt.imag >= d_min:
                    break
                d_min = min(d_min, abs(alt))

            min_stack.append(ele)

        return d_min

    def solve(self):
        return self.closest_pair(array=self.p_list, array_length=self.p_num)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    case = ClosestPair(in_data=_input)
    print('{:.6f}'.format(case.solve()))

Submission status: Runtime Error

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

"""
input:
3
0.0 0.0
2.0 0.0
1.0 1.0

output:
1.41421356237
"""

import sys
from operator import attrgetter


class ClosestPair(object):
    def __init__(self, in_data):
        """
        Init closest pairs points set.
        """
        self.p_num = int(in_data[0])
        points = map(lambda x: x.split(), in_data[1:])
        p_list = [complex(float(x), float(y)) for x, y in points]
        # pre_sort by axis_X
        p_list.sort(key=attrgetter('real'))
        self.p_list = p_list

    def closest_pair(self, array, array_length):
        if array_length <= 1:
            return float('inf')
        mid_idx = array_length // 2
        div_line = array[mid_idx].real
        d_min = min(self.closest_pair(array[:mid_idx], mid_idx),
                    self.closest_pair(array[mid_idx:], array_length - mid_idx))

        # sort array_part by axis_Y while recursively comparing
        array.sort(key=attrgetter('imag'))

        min_stack = list()
        for ele in array:
            size = len(min_stack)

            # eliminate p which distance(p,div_line) >= d
            if abs(ele.real - div_line) >= d_min:
                continue

            for j in range(size):
                alt = ele - min_stack[size - j - 1]
                if alt.imag >= d_min:
                    break
                d_min = min(d_min, abs(alt))

            min_stack.append(ele)

        return d_min

    def solve(self):
        return self.closest_pair(array=self.p_list, array_length=self.p_num)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    case = ClosestPair(in_data=_input)
    print('{:.6f}'.format(case.solve()))

Submission status: Runtime Error

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 = [0] * g.V
        self.head = [-1] * g.V
        self.heavy = [-1] * g.V
        self.parent = [-1] * g.V
        self.dfs(root)
        self.bfs(root)

    def dfs(self, v, par=-1):
        self.parent[v] = par
        sub, max_sub = 1, 0
        for e in self.g.E[v]:
            child = e.dst
            if child != par:
                child_sub = self.dfs(child, v)
                sub += child_sub
                if child_sub > max_sub:
                    max_sub = child_sub
                    self.heavy[v] = child
        return sub

    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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)


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 = [0] * g.V
        self.head = [-1] * g.V
        self.heavy = [-1] * g.V
        self.parent = [-1] * g.V
        self.dfs(root)
        self.bfs(root)

    def dfs(self, v, par=-1):
        self.parent[v] = par
        sub, max_sub = 1, 0
        for e in self.g.E[v]:
            child = e.dst
            if child != par:
                child_sub = self.dfs(child, v)
                sub += child_sub
                if child_sub > max_sub:
                    max_sub = child_sub
                    self.heavy[v] = child
        return sub

    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: Runtime Error

Solution code:
from math import log2


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


def dfs(tree, v, p, d):
    parent[0][v] = p
    depth[v] = d
    for child in tree[v]:
        if child != p:
            dfs(tree, child, v, d + 1)


def get(u, v):
    du, dv = depth[u], depth[v]
    if du > dv:
        u, v = v, u
        du, dv = dv, du
    for k in range(logn):
        if (dv - du) >> k & 1:
            v = parent[k][v]
    if u == v:
        return u
    for k in range(logn - 1, -1, -1):
        pk = parent[k]
        if pk[u] != pk[v]:
            u, v = pk[u], pk[v]
    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: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

from math import log2


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


def dfs(tree, v, p, d):
    parent[0][v] = p
    depth[v] = d
    for child in tree[v]:
        if child != p:
            dfs(tree, child, v, d + 1)


def get(u, v):
    du, dv = depth[u], depth[v]
    if du > dv:
        u, v = v, u
        du, dv = dv, du
    for k in range(logn):
        if (dv - du) >> k & 1:
            v = parent[k][v]
    if u == v:
        return u
    for k in range(logn - 1, -1, -1):
        pk = parent[k]
        if pk[u] != pk[v]:
            u, v = pk[u], pk[v]
    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: Runtime Error

Solution code:
from collections import deque
n = input()

C = [None]*n
P = [None]*n
for i in xrange(n):
    ipt = map(int, raw_input().split())
    C[i] = ipt[1:]
    for c in C[i]:
        P[c] = i
LEV = (n+1).bit_length()
parent = [[None]*(LEV + 1) for i in xrange(n)]
for i in xrange(n):
    parent[i][0] = P[i]
for k in xrange(1, LEV):
    for i in xrange(n):
        if parent[i][k] is None:
            parent[i][k+1] = None
        else:
            parent[i][k+1] = parent[parent[i][k]][k]
depth = [None]*n
deq = deque()
deq.append(0)
depth[0] = 0
while deq:
    v = deq.popleft()
    for c in C[v]:
        deq.append(c)
        depth[c] = depth[v] + 1

q = input()
for t in xrange(q):
    u, v = map(int, raw_input().split())
    if not depth[u] < depth[v]:
        u, v = v, u
    for k in xrange(LEV+1):
        if ((depth[v] - depth[u]) >> k) & 1:
            v = parent[v][k]
    if u == v:
        print u
        continue

    for k in xrange(LEV, -1, -1):
        if parent[u][k] != parent[v][k]:
            u = parent[u][k]
            v = parent[v][k]
    print parent[u][0]

Submission status: Runtime Error

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, 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 = 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, depth))

Submission status: Runtime Error

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