const INF: usize = 1001001001001001001;
type Graph = Vec<Vec<usize>>;
pub struct LCA {
double: Vec<Vec<usize>>,
depth: Vec<usize>,
}
impl LCA {
pub fn new(tree: &Graph, root: usize) -> Self {
let V = tree.len(); let logV = {
let mut logv = 0;
while (V >> logv) > 0 {
logv += 1;
}
logv
};
let mut double = vec![vec![0; V]; logV]; let mut depth = vec![INF; V]; depth[0] = 0;
Self::dfs(root, &mut double[0], &mut depth, tree);
for i in 1..logV {
for j in 0..V {
double[i][j] = double[i - 1][double[i - 1][j]];
}
}
Self { double, depth }
}
fn dfs(u: usize, par: &mut Vec<usize>, depth: &mut Vec<usize>, tree: &Graph) {
for &v in &tree[u] {
if depth[v] != INF {
continue;
}
depth[v] = depth[u] + 1;
par[v] = u;
Self::dfs(v, par, depth, tree);
}
}
pub fn get_lca(&self, mut u: usize, mut v: usize) -> usize {
if self.depth[u] < self.depth[v] {
std::mem::swap(&mut u, &mut v);
}
for k in 0..self.double.len() {
if ((self.depth[u] - self.depth[v]) >> k) & 1 == 1 {
u = self.double[k][u];
}
}
if u == v {
return u;
}
for k in (0..self.double.len()).rev() {
if self.double[k][u] != self.double[k][v] {
u = self.double[k][u];
v = self.double[k][v];
}
}
self.double[0][u]
}
pub fn dist(&self, u: usize, v: usize) -> usize {
let o = self.get_lca(u, v);
(self.depth[u] - self.depth[o]) + (self.depth[v] - self.depth[o])
}
}