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:
import math

def lca(x, y):
    if d[x] < d[y]:
        x,y = y,x
    dy = d[y]
    k = d[x]-dy
    while k:
        x = p[x][int(math.log(k,2))]
        k = d[x]-dy

    if x == y:
        return x

    for i in range(h)[::-1]:
        if p[x][i] != p[y][i]:
            x = p[x][i]
            y = p[y][i]
    return p[x][0]
if __name__ == "__main__":
    n = int(input())
    d = [0]*n
    d[0] = 1
    p = [[] for i in range(n)]
    p[0].append(0)
    for i in range(n):
        vi = map(int, input().split()[1:])
        nd = d[i]+1
        for j in vi:
            p[j].append(i)
            d[j] = nd
    h = int(math.log(max(d),2))+1
    for i in range(h-1):
        for x in range(n):
            p[x].append(p[p[x][i]][i])
    q = int(input())
    for _ in range(q):
        x,y = map(int, input().split())
        print(lca(x,y))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

# n = int(input())
# G = [[] for i in range(n)]
# for i in range(n-1):
#   a,b = map(int,input().split())
#   # a-=1;b-=1
#   G[a].append(b)
#   G[b].append(a)

n=int(input())
G = [[] for i in range(n)]
for i in range(n):
  data = list(map(int,input().split()))
  for j in range(1,len(data)):
    G[i].append(data[j])

depth = [0] * n
parent = [[0] * n for i in range(20)]
def setdepth(node,pre,d):
  depth[node] = d
  parent[0][node] = pre
  for vi in G[node]:
    if vi == pre: continue
    setdepth(vi,node,d + 1)

setdepth(0,-1,0)

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

def lca(u,v):
  # 高度調整
  if depth[u] > depth[v]: u,v = v,u
  for k in range(20):
    if (depth[v] - depth[u]) >> k & 1:
      v = parent[k][v]
  # 2部探索
  if u == v:
    return u
  for k in range(19,-1,-1):
    if parent[k][u] != parent[k][v]:
      u = parent[k][u]
      v = parent[k][v]
  return parent[0][u]

Q = int(input())
for _ in range(Q):
  x,y = map(int,input().split())
  # x-=1;y-=1
  print(lca(x,y))
  # print(depth[x] + depth[y] - 2 * depth[lca(x,y)] + 1)

Submission status: Accepted

Solution code:
import math
from collections import deque

def create_table(N, A):
    num_block = int(-(-math.log2(N)//1)) + 1
    dp = [[-1]*num_block for i in range(N)]
    for i in range(N):
        dp[i][0] = i
    for k in range(1, num_block):
        for i in range(N):
            e = min(N-1, i + (1 << (k - 1)))
            former = dp[i][k-1]
            later = dp[e][k-1]
            if A[former] > A[later]:
                dp[i][k] = later
            else:
                dp[i][k] = former
            if e == N-1:
                break
    return dp

def query(i, j, dp, A):
    if i == j:
      return i
    length = int(math.log2(abs(i-j)))
    former = dp[i][length]
    later = dp[j-(1<<length)+1][length]
    if A[former] > A[later]:
        return later
    return former
      
def run():
  N = int(input())
  g = {}
  for n in range(N):
    kc = list(map(int, input().split()))
    g[n] = kc[1:]
  Q = int(input())
  uv = [tuple(map(int, input().split())) for q in range(Q)]
  euler = []
  depths = []
  order = [-1]*N
  def dfs(now, pred, d):
    stacks = deque([(now, pred, d)])
    while stacks:
      now, pred, d = stacks.pop()
      euler.append(now)
      depths.append(d)
      if order[now] != -1:
        continue
      if order[now] == -1:
        order[now] = len(euler) - 1
      for nxt in g[now]:
        if nxt == pred:
          continue
        stacks.append((now, pred, d))
        stacks.append((nxt, now, d+1))
  dfs(0, -1, 0)
  #RMQ
  len_li = len(depths)
  dp = create_table(len_li, depths)
  #LCA
  for u, v in uv:
    o1, o2 = order[u], order[v]
    o1, o2 = min([o1, o2]), max([o1, o2])
    o = query(o1, o2, dp, depths)
    print(euler[o])
    if len(uv) == 1:
      exit()
  
if __name__ == '__main__':
  run()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


class SegTree():
    def __init__(self, l, INF):
        self.inf = INF

        N = len(l)
        v = 1
        while v<N:
            v *= 2

        self.size = v
        self.node = [self.inf] * (2*self.size-1)
        for i in range(N): # 最下段を埋める
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = min(self.node[2*i+1], self.node[2*i+2]) # 上段の更新をする

    def get(self, left, right, k=0, l=0, r=-1):
        if r < 0:
            r = self.size

        if (r <= left or right <= l):
            return self.inf
        if (left <= l and r <= right):
            return self.node[k]

        vl = self.get(left, right, 2*k+1, l, (l+r)//2)
        vr = self.get(left, right, 2*k+2, (l+r)//2, r)
        return min(vl, vr)

    def update(self, x, v):
        x += self.size-1
        self.node[x] = v

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


class LCA():
    def __init__(self, N, G):
        self.depth = [0] * (N+1)
        self.euler_tour = []
        self.G = G
    
        self.idx = {}
        self._currentIndex = 0

        self._dfs(0, 0, 0)
        self.tree = SegTree(self.euler_tour, (2**31-1, 2**31-1))
    
    def _dfs(self, v, p, d):
        self.euler_tour.append((d, v))
        self.idx[v] = self._currentIndex
        self._currentIndex += 1

        self.depth[v] = d
        for u in self.G[v]:
            if u==p:continue
            self._dfs(u, v, d+1)
            self.euler_tour.append((d, v))
            self._currentIndex += 1
    
    def get(self, u, v):
        a, b = self.idx[u], self.idx[v]
        a, b = (a, b) if a<b else (b, a)
        return self.tree.get(a, b+1)[1]


if __name__ == "__main__":
    n = int(input())
    G = {i:[] for i in range(n)}
    for i in range(n):
        k, *l = map(int, input().split())
        G[i] = l
        for j in l:
            G[j].append(i)
    lca = LCA(n, G)
    q = int(input())
    for _ in range(q):
        u, v = map(int, input().split())
        print(lca.get(u, v))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class Tree():
    def __init__(self,n,edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0]-1].append(e[1]-1)
            self.tree[e[1]-1].append(e[0]-1)

    def setroot(self,root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node]+1
                    stack.append(adj)

    def construct_lca(self):
        L = (self.n-1).bit_length()
        self.k_parent = [self.parent]
        prev = self.parent
        for k in range(L):
            array = [0 for _ in range(self.n)]
            for i in range(self.n):
                if prev[i] == -1:
                    continue
                array[i] = prev[prev[i]]
            self.k_parent.append(array)
            prev = array

    def lca(self,u,v):
        d = self.depth[v]-self.depth[u]
        if d < 0: u,v,d = v,u,-d
        for k in self.k_parent:
            if d & 1: v = k[v]
            d >>= 1
        if u == v:
            return u
        for k in reversed(self.k_parent):
            pu,pv = k[u],k[v]
            if pu != pv: u,v = pu,pv
        return self.k_parent[0][u]

N = int(input())
E = []

for i in range(N):
    raw_input = list(map(int,input().split()))
    for j in range(raw_input[0]):
        E.append((i+1,raw_input[j+1]+1))

t = Tree(N,E)
t.setroot(0)
t.construct_lca()

Q = int(input())
A = []

for _ in range(Q):
    u,v = map(int,input().split())
    A.append(t.lca(u,v))

print(*A,sep='\n')

Submission status: Accepted

Solution code:
# 参考　https://tjkendev.github.io/procon-library/python/graph/lca-segment-tree.html

# N: 頂点数
# G[v]: 頂点vの子頂点 (親頂点は含まない)

import sys
sys.setrecursionlimit(10**7)

N = int(input())
G = [[] for _ in range(N)]
for v in range(N):
    for j, nv in enumerate(map(int, input().split())):
        if j == 0:
            continue
        G[v].append(nv)  

# Euler Tour の構築
S = []
F = [0]*N
depth = [0]*N
def dfs(v, d):
    F[v] = len(S)
    depth[v] = d
    S.append(v)
    for w in G[v]:
        dfs(w, d+1)
        S.append(v)
dfs(0, 0)

# 存在しない範囲は深さが他よりも大きくなるようにする
INF = (N, None)

# LCAを計算するクエリの前計算
M = 2*N
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])

# LCAの計算 (generatorで最小値を求める)
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1

# LCAの計算 (外から呼び出す関数)
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv + 1))[1]]

ans_list = []

q = int(input())
for _ in range(q):
    u, v = map(int, input().split())
    ans = query(u, v)
    ans_list.append(ans)

print(*ans_list, sep="\n")

Submission status: Accepted

Solution code:
# AOJ GRL_5_C Lowest Common Ancestor
# calculate LCA O(logN) for each query

# start form 0 node

# prev[i][k]: 2^k parent of node i 
# Depth[i]: depth of node i from 0


import sys
input = sys.stdin.readline

N = int(input())
Log_N = (N-1).bit_length()

prev = [[-1]*(Log_N+1) for _ in range(N)]
graph = [[] for _ in range(N)]
for i in range(N):
    K, *A = map(int, input().split())
    graph[i] = A
    for a in A:
        prev[a][0] = i

Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]


# BFS
Depth = [-1]*N
q = [0]
Depth[0] = 0
d = 0
while q:
    qq = []
    d += 1
    for p in q:
        for np in graph[p]:
            if Depth[np] == -1:
                Depth[np] = d
                qq.append(np)
    q = qq


# construct
for k in range(Log_N):
    for i in range(N):
        if prev[i][k] == -1:
            prev[i][k+1] = -1
        else:
            prev[i][k+1] = prev[prev[i][k]][k]

# LCA
def LCA(u, v):
    dd = Depth[v] - Depth[u]
    if dd < 0:
        u, v = v, u
        dd = -dd
    
    # set same depth
    for k in range(Log_N+1):
        if dd & 1:
            v = prev[v][k]
        dd >>= 1
    
    if u == v:
        return u
    
    for k in reversed(range(Log_N)):
        pu = prev[u][k]
        pv = prev[v][k]
        if pu != pv:
            u, v = pu, pv
    
    return prev[u][0]


for a, b in Query:
    print(LCA(a, b))

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    depth[0] = 0
    queue = deque([])
    queue.append(0)
    
    while queue:
        current_node = queue.popleft()
        
        for next_node in adj_list[current_node]:
            if depth[next_node] == -1:
                parent[0][next_node] = current_node
                depth[next_node] = depth[current_node] + 1
                queue.append(next_node)
    
def init():
    bfs() #initialize depth and parent[0]
    
    for k in range(1, log_size):
        for v in range(N):
            if parent[k-1][v] < 0:
                parent[k][v] = -1
            else:
                parent[k][v] = parent[k-1][parent[k-1][v]]

def lca(u, v): #return lowest common ancestor when 0 is root node
    if depth[u] > depth[v]:
        u, v = v, u
    
    for k in range(log_size):
        if (depth[v]-depth[u])>>k & 1:
            v = parent[k][v]
    
    if u == v:
        return u
    
    for k in range(log_size-1, -1, -1):
        if parent[k][u] != parent[k][v]:
            u = parent[k][u]
            v = parent[k][v]
    
    return parent[0][u]
    
N = int(input())
log_size = N.bit_length() #ceil(log)
depth = [-1] * N
parent = [[-1] * N for _ in range(log_size)]
adj_list = [[] for _ in range(N)]

for i in range(N):
    kc = list(map(int, input().split()))
    
    for ci in kc[1:]:
        adj_list[i].append(ci)
        adj_list[ci].append(i)

init()
q = int(input())

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

Submission status: Accepted

Solution code:
from collections import deque


class LowestCommonAncestor():
    """根付き木に対して、二頂点の共通の祖先で最も近いところにある頂点を求める
    初期化(ダブリング配列parent[k][v]の構築): O(NlogN)
    lcaを求めるクエリ: O(logN)
    """
    
    def __init__(self, tree, root):
        self.n = len(tree)
        self.depth = [0] * self.n
        self.log_size = (self.n).bit_length()
        self.parent = [[-1] * self.n for i in range(self.log_size)]

        # 親を2^0回たどって到達する頂点、つまり現在の頂点に対する親の頂点を求める
        # parent[0][現在の頂点] = 親の頂点
        q = deque([(root, -1, 0)]) # (現在の地点, 親の頂点, 現在の頂点と親の頂点間の距離) 
        while q:
            v, par, dist = q.pop()
            self.parent[0][v] = par
            self.depth[v] = dist
            for child_v in tree[v]:
                if child_v != par:
                    self.depth[child_v] = dist + 1
                    q.append((child_v, v, dist + 1))

        # ダブリングで親を2^k回たどって到達する頂点を求める
        for k in range(1, self.log_size):
            for v in range(self.n):
                self.parent[k][v] = self.parent[k-1][self.parent[k-1][v]]
            
    def lca(self, u, v):
        # u, vのうち深いところにある方から|depth[u] - depth[v]|だけ親をたどる
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        for k in range(self.log_size):
            if (self.depth[v] - self.depth[u] >> k) & 1:
                v = self.parent[k][v]
        if u == v:
            return u
          
        # 二分探索でLCAを求める
        for k in reversed(range(self.log_size)):
            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())
info = [list(map(int, input().split())) for i in range(n)]
tree = [[] for i in range(n)]
for i in range(n):
    for j in info[i][1:]:
        tree[i].append(j)
        tree[j].append(i)

lca = LowestCommonAncestor(tree, 0)

q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    u, v = query[i]
    print(lca.lca(u, v))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
from math import log2
from collections import deque
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    LogN = int( log2(N))+1 # log of edge number
    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: #calculate depth and calculate the parent of each vertex by 2**0 = 1
        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()

Submission status: Accepted

Solution code:
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:
    # http://tsutaj.hatenablog.com/entry/2017/03/29/204841
    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

        # size 以上である最小の 2 冪
        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 = []
    # Overflow 回避のためループで
    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[v]: trails が v となる trails / depths のインデックス
ids = [0] * N
for i, v in enumerate(trails):
    ids[v] = i

# depths[v] から depths[u] までの最小値が LCA
st = SegmentTree(size=len(depths), fn=min, default=(IINF, -1), initial_values=list(zip(depths, trails)))

# RmQ
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):
        # parents[v]: the parent of the vertex v
        # depth[v]: the depth of the vertex v from the root
        # dist[v]: the distance of the vertex v from the 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):
        # O(N log N) time
        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):
        # O(log N) time
        # the depth of v is set to be no less than that of u
        if self.depth[u] > self.depth[v]: u, v = v, u
        # find the ancestor of v with the same depth as that of 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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))