tipstar0125
commented
1 year ago #[derive(Debug, Clone)]
struct LowestCommonAncestor<'a> {
size: usize,
edge: &'a Vec<Vec<usize>>,
root: usize,
K: usize,
depth: Vec<usize>,
parent: Vec<Vec<isize>>,
}
impl<'a> LowestCommonAncestor<'a> {
fn new(edge: &'a Vec<Vec<usize>>, root: usize) -> Self {
let size = edge.len();
let mut K = 1;
while 1 << K < size {
K += 1;
}
let depth = vec![0; size];
let parent = vec![vec![-1; size]; K];
LowestCommonAncestor {
size,
edge,
root,
K,
depth,
parent,
}
}
fn build(&mut self) {
self.dfs(self.root, -1, 0);
for k in 0..self.K - 1 {
for v in 0..self.size {
if self.parent[k][v] < 0 {
self.parent[k + 1][v] = -1;
} else {
self.parent[k + 1][v] = self.parent[k][self.parent[k][v] as usize];
}
}
}
}
fn dfs(&mut self, v: usize, p: isize, d: usize) {
self.parent[0][v] = p;
self.depth[v] = d;
for &u in &self.edge[v] {
if u as isize != p {
self.dfs(u, v as isize, d + 1);
}
}
}
fn query(&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.K {
if ((self.depth[u] - self.depth[v]) >> k & 1) > 0 {
u = self.parent[k][u] as usize;
}
}
if u == v {
return u;
}
for k in (0..self.K).rev() {
if self.parent[k][u] != self.parent[k][v] {
u = self.parent[k][u] as usize;
v = self.parent[k][v] as usize;
}
}
self.parent[0][u] as usize
}
}
参考：https://algo-logic.info/lca/ ダブリングissue：https://github.com/tipstar0125/atcoder/issues/17 AOJジャッジ：https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_C 解答：https://onlinejudge.u-aizu.ac.jp/solutions/problem/GRL_5_C/review/8500716/tipstar0125/Rust