pub fn subtree_size(p: usize, u: usize, G: &Vec<Vec<usize>>, W: &[usize], res: &mut [usize]) {
res[u] += W[u];
for &v in &G[u] {
if p == v {
continue;
}
subtree_size(u, v, G, W, res);
res[u] += res[v];
}
}
pub fn get_centroid(p: usize, u: usize, G: &Vec<Vec<usize>>, S: &[usize], root: usize) -> usize {
let mut is_centroid = true;
for &v in &G[u] {
if v == p {
continue;
}
let res = get_centroid(u, v, G, S, root);
if res < usize::MAX {
return res;
}
if S[v] > S[root] / 2 {
is_centroid = false;
}
}
if (S[root] - S[u]) > S[root] / 2 {
is_centroid = false;
}
if is_centroid {
u
} else {
usize::MAX
}
}