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  k 0  c 1  c 2 ... c k 0  k 1  c 1  c 2 ... c k 1 : k n-1  c 1  c 2 ... c k n-1  q  u 1  v 1  u 2  v 2 : u q  v q  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. k i is the number of children of node i , and c 1 , ... c k i are node IDs of 1st, ... k th 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

Solution (Python):
from math import log2


def build():
    global parent
    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():
    global depth, parent, tree
    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 lca(u: int, v: int) -> int:
    global depth, parent
    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:None:-1]:
        pku, pkv = pk[u], pk[v]
        if pku != pkv:
            u, v = pku, pkv
    return parent[0][u]


if __name__ == "__main__":
    n = int(input())
    tree = []
    for _ in range(n):
        _, *children = map(lambda x: int(x), input().split())
        tree.append(set(children))

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

    q = int(input())
    for _ in range(q):
        u, v = map(lambda x: int(x), input().split())
        print(lca(u, v))

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

readline = sys.stdin.readline
write = sys.stdout.write

N = int(readline())
G = [None]*N
for v in range(N):
    k, *G[v] = map(int, readline().split())

S = []

FS = [0]*N
depth = [0]*N

*it, = map(iter, G)
P = [-1]*N

stk = [0]
depth[0] = 0
FS[0] = 0
while stk:
    v = stk[-1]
    p = P[v]
    S.append(v)

    w = next(it[v], -1)
    while w != -1:
        if w != p:
            P[w] = v
            depth[w] = len(stk)
            FS[w] = len(S)
            stk.append(w)
            break
        w = next(it[v], -1)
    else:
        stk.pop()

L = len(S)
lg = [0]*(L + 1)
for i in range(2, L+1):
    lg[i] = lg[i >> 1] + 1
st = [None]*(lg[L] + 1)
st0 = st[0] = S
b = 1
for i in range(lg[L]):
    st0 = st[i+1] = [p if depth[p] <= depth[q] else q for p, q in zip(st0, st0[b:])]
    b <<= 1

def query(u, v):
    x = FS[u]; y = FS[v]
    if x > y:
        x, y = y, x
    l = lg[y - x + 1]
    px = st[l][x]; py = st[l][y - (1 << l) + 1]
    return px if depth[px] <= depth[py] else py

Q = int(readline())
ans = []
for q in range(Q):
    u, v = map(int, readline().split())
    ans.append(query(u, v))
write("\n".join(map(str, ans)))
write("\n")

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


class LCA:
    def __init__(self, n):
        self.edges = [[] for _ in range(n)]
        self.n = n
        self.logn = len(bin(n)[2:])
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n

    def add(self, u, v):
        self.edges[u].append(v)
        self.edges[v].append(u)

    def initialize(self, root=0):
        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.edges[v]:
            if e != p:
                self.dfs(e, v, dep + 1)

    def get_lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        dep_diff = self.depth[v] - self.depth[u]
        for k in range(self.logn):
            if (dep_diff >> k & 1) != 0:
                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())
lca = LCA(N)
for i in range(N):
    kc = list(map(int, input().split()))
    k = kc[0]
    for c in kc[1:]:
        lca.add(i, c)

lca.initialize()
Q = int(input())
for _ in range(Q):
    u, v = map(int, input().split())
    print(lca.get_lca(u, v))

Solution (Python):
from math import log2
from collections import deque
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    LogN = int( log2(N))+1 
    E = [ list( map( int, input().split()))[1:] for i in range(N)]
    parent = [[-1]*(LogN) for _ in range(N)]
    start = 0
    deq = deque([0])
    depth = [-1]*N
    depth[start] = 0
    while deq: 
        v = deq.popleft()
        nextdepth = depth[v] + 1
        for w in E[v]:
            if depth[w] == -1:
                depth[w] = nextdepth
                parent[w][0] = v
                deq.append(w)

    for k in range(LogN-1):
        for v in range(N):
            if (parent[v][k] < 0):
                parent[v][k+1] = -1
            else:
                parent[v][k+1] = parent[ parent[v][k]][k]

    Q = int( input())
    for _ in range(Q):
        u, v = map( int, input().split())
        if depth[u] > depth[v]:
            u, v = v, u
        for k in range(LogN):
            if( (depth[v] - depth[u]) >> k & 1):
                v = parent[v][k]
        if u == v:
            print(u)
            continue
        for k in range(LogN-1, -1, -1):
            if parent[u][k] != parent[v][k]:
                u = parent[u][k]
                v = parent[v][k]
        print(parent[u][0])

if __name__ == '__main__':
    main()

Solution (Python):
import operator
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
graph = [[] for _ in range(N)]
for i in range(N):
    _, *c = list(map(int, sys.stdin.readline().split()))
    graph[i] = c
Q = int(sys.stdin.readline())
UV = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]


class SegmentTree:
    
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


def tree_eulerian_trail(graph, root=0):
    """
    木のオイラー路; オイラーツアー
    :param list of (list of int) graph:
    :param int root:
    :return: (trails, depths)
    :rtype: (list of int, list of int)
    """
    
    trails = []
    
    depths = []
    
    stack = [(root, 0, True)]
    while stack:
        v, d, forward = stack.pop()
        trails.append(v)
        depths.append(d)
        if not forward:
            continue
        for u in graph[v]:
            stack.append((v, d, False))
            stack.append((u, d + 1, True))
    return trails, depths


trails, depths = tree_eulerian_trail(graph, 0)

ids = [0] * N
for i, v in enumerate(trails):
    ids[v] = i


st = SegmentTree(size=len(depths), fn=min, default=(IINF, -1), initial_values=list(zip(depths, trails)))


for u, v in UV:
    iu, iv = ids[u], ids[v]
    if iu > iv:
        iu, iv = iv, iu
    _, lca = st.get(iu, iv + 1)
    print(lca)

Solution (Python):
import math
from collections import deque

def input(f):
    n, = map(int, f.readline().split())
    k = [None for _ in range(n)]
    c = [[] for _ in range(n)]
    for i in range(n):
        tmp = map(int, f.readline().split())
        k[i] = tmp.pop(0)
        c[i] = tmp[:]
    q, = map(int, f.readline().split())
    u = [None for _ in range(q)]
    v = [None for _ in range(q)]
    for i in range(q):
        u[i], v[i] = map(int, f.readline().split())
    
    return n, k, c, q, u, v

def solve(n, k, c, q, u, v):
    graph = [[] for _ in range(n)]
    for i in range(n):
        for j in range(k[i]):
            graph[i].append(c[i][j])
    
    logn = int(math.log(n, 2))+1
    pa = [[None for _ in range(n)] for _ in range(logn+1)]
    depth = [None for _ in range(n)]
    
    def build():
        que = deque()
        que.append(0)
        depth[0] = 0
        while que:
            cur = que.popleft()
            for child in c[cur]:
                depth[child] = depth[cur] + 1
                que.append(child)
            
        for i in range(n):
            for child in c[i]:
                pa[0][child] = i
        for i in range(logn):
            for j in range(n):
                if pa[i][j] != None:
                    pa[i+1][j] = pa[i][pa[i][j]]
    
    def query(u, v):
        while depth[u] != depth[v]:
            if depth[v] < depth[u]:
                u, v = v, u
            d = depth[v] - depth[u]
            for k in range(logn):
                if d & 1:
                    v = pa[k][v]
                d = d >> 1
        for nk in range(logn):
            k = logn - nk - 1
            if pa[k][u] != pa[k][v]:
                u = pa[k][u]
                v = pa[k][v]
        if u == v:
            return u
        return pa[0][u]
    
    depth[0] = 0
    build()

    for i in range(q):
        yield query(u[i], v[i])
    
with open('/dev/stdin') as f:
    for res in solve(*input(f)):
        print(res)

Solution (Python):
from collections import defaultdict

class Tree:
    def __init__(self, N):
        self.N = N
        self.D = (self.N-1).bit_length()
        self.E = defaultdict(dict)
    
    def add_edge(self, init, end, weight, undirected=False):
        self.E[init][end] = weight
        if undirected: self.E[end][init] = weight
    
    def dfs(self, root):
        
        
        
        self.parent = [None] * self.N
        self.depth = [-1] * self.N
        self.dist = [float('inf')] * self.N
        self.parent[root] = -1; self.depth[root] = 0; self.dist[root] = 0;
        stack = [root]
        while stack:
            v = stack.pop()
            for u in self.E[v].keys():
                if self.depth[u] != -1: continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self.dist[u] = self.dist[v] + self.E[v][u]
                stack.append(u)
    
    def doubling(self):
        
        self.next = [self.parent]
        for d in range(1, self.D):
            self.next.append([self.next[d-1][self.next[d-1][v]] if self.next[d-1][v] != -1 else -1 for v in range(self.N)])
    
    def lca(self, u, v):
        
        
        if self.depth[u] > self.depth[v]: u, v = v, u
        
        diff = self.depth[v] - self.depth[u]
        for i in range(diff.bit_length()):
            if diff & 1: v = self.next[i][v]
            diff >>= 1
        if u == v: return u
        for i in range(self.D-1, -1, -1):
            pu, pv = self.next[i][u], self.next[i][v]
            if pu != pv: u, v = pu, pv
        return self.next[0][u]

n = int(input())
tr = Tree(n)
for i in range(n):
    k, *C, = map(int, input().split())
    for c in C:
        tr.add_edge(i, c, 1, undirected=True)
tr.dfs(0)
tr.doubling()
q = int(input())
for _ in range(q):
    u, v = map(int, input().split())
    print(tr.lca(u, v))

Solution (Python):
import sys
from math import log2

sys.setrecursionlimit(int(1e7))


def doubling():
    dfs(0, -1, 0)
    p0 = parent[0]
    for p1 in parent[1:]:
        for i in range(n):
            pi = p0[i]
            p1[i] = -1 if pi < 0 else p0[pi]
        p0 = p1


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


def lca(u, v):
    du, dv = depth[u], depth[v]
    if du > dv:
        u, v = v, u
        du, dv = dv, du
    for i, p in enumerate(parent):
        if (dv - du) >> i & 1:
            v = p[v]
    if u == v:
        return u
    for p in parent[logn - 1:None:-1]:
        pu, pv = p[u], p[v]
        if pu != pv:
            u, v = pu, pv
    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

doubling()

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

Solution (Python):
from bisect import bisect_right as br
import sys
sys.setrecursionlimit(100000)
n = int(input())
parent = [[None] * 20 for _ in range(n)]
for i in range(n):
  clst = list(map(int, input().split()))[1:]
  for c in clst:
    parent[c][0] = i

for i in range(1, 20):
  for j in range(n):
    if parent[j][i - 1] != None:
      parent[j][i] = parent[parent[j][i - 1]][i - 1]

height = [None for _ in range(n)]
height[0] = 0

def make_height(x):
  if height[x] != None:return
  if height[parent[x][0]] != None:
    make_height(parent[x][0])
  height[x] = height[parent[x][0]] + 1

for i in range(n):
  make_height(i)

bins = [2 ** i for i in range(20)]

def retro(p, num):
  if num == 0:return p
  ind = br(bins, num) - 1
  return retro(parent[p][ind], num - bins[ind])

def _lca(u, v):
  if u == v:
    return u
  for i in range(1, 20):
    if parent[u][i] == parent[v][i]:
      return _lca(parent[u][i - 1], parent[v][i - 1])

def lca(u, v):
  if height[u] < height[v]:
    v = retro(v, height[v] - height[u])
  if height[u] > height[v]:
    u = retro(u, height[u] - height[v])
  return _lca(u, v)

q = int(input())
for _ in range(q):
  u, v = map(int, input().split())
  print(lca(u, v))

Solution (Python):
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)