cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: test/aoj/grl/grl_5_c_lca_table_recursive.test.py

Depends on

Code

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_5_C

def main():
    N, = read()
    T = []
    for _ in range(N):
        k, *adj = read()
        T.append(adj)
    lca = LCATable(T, 0)
    Q, = read()
    for _ in range(Q):
        u, v = read()
        write(lca.query(u,v)[0])

from cp_library.alg.tree.lca_table_recursive_cls import LCATable
from cp_library.io.read_int_fn import read
from cp_library.io.write_fn import write

if __name__ == '__main__':
    main()
# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_5_C

def main():
    N, = read()
    T = []
    for _ in range(N):
        k, *adj = read()
        T.append(adj)
    lca = LCATable(T, 0)
    Q, = read()
    for _ in range(Q):
        u, v = read()
        write(lca.query(u,v)[0])

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''


import sys
sys.setrecursionlimit(10**6)
import pypyjit
pypyjit.set_param("max_unroll_recursion=-1")
from typing import Generic, Callable
from typing import TypeVar
_T = TypeVar('T')



class SparseTable(Generic[_T]):
    def __init__(st, op: Callable[[_T,_T],_T], arr: list[_T]):
        st.N = N = len(arr)
        st.log = N.bit_length()
        st.op = op
        st.data = data = [0] * (st.log*N)
        data[:N] = arr
        for i in range(1,st.log):
            a, b, c = i*N, (i-1)*N, (i-1)*N + (1 << (i-1))
            for j in range(N - (1 << i) + 1):
                data[a+j] = op(data[b+j], data[c+j])

    def query(st, l: int, r: int) -> _T:
        k = (r-l).bit_length() - 1
        return st.op(st.data[k*st.N + l], st.data[k*st.N + r - (1<<k)])

class LCATable(SparseTable):
    def __init__(self, T, root):
        self.start = [-1] * len(T)
        euler_tour = []
        depths = []
        
        def dfs(u: int, p: int, depth: int):
            self.start[u] = len(euler_tour)
            euler_tour.append(u)
            depths.append(depth)
            
            for child in T[u]:
                if child != p:
                    dfs(child, u, depth + 1)
                    euler_tour.append(u)
                    depths.append(depth)
        
        dfs(root, -1, 0)
        super().__init__(min, list(zip(depths, euler_tour)))

    def query(self, u, v) -> tuple[int,int]:
        l, r = min(self.start[u], self.start[v]), max(self.start[u], self.start[v])+1
        d, a = super().query(l, r)
        return a, d

    def distance(self, u, v) -> int:
        l, r = min(self.start[u], self.start[v]), max(self.start[u], self.start[v])+1
        d, _ = super().query(l, r)
        return self.depth[l] + self.depth[r] - 2*d


def read(shift=0, base=10):
    return [int(s, base) + shift for s in input().split()]
import os
from io import BytesIO, IOBase


class FastIO(IOBase):
    BUFSIZE = 8192
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        BUFSIZE = self.BUFSIZE
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        BUFSIZE = self.BUFSIZE
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    stdin: 'IOWrapper' = None
    stdout: 'IOWrapper' = None
    
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable

    def write(self, s):
        return self.buffer.write(s.encode("ascii"))
    
    def read(self):
        return self.buffer.read().decode("ascii")
    
    def readline(self):
        return self.buffer.readline().decode("ascii")

sys.stdin = IOWrapper.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper.stdout = IOWrapper(sys.stdout)

def write(*args, **kwargs):
    '''Prints the values to a stream, or to stdout_fast by default.'''
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", IOWrapper.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()

if __name__ == '__main__':
    main()
Back to top page