competitive/tree/
tree_centroid.rs

1use super::UndirectedSparseGraph;
2
3impl UndirectedSparseGraph {
4    pub fn tree_centroid(&self) -> usize {
5        fn dfs(g: &UndirectedSparseGraph, u: usize, p: usize) -> (usize, usize) {
6            let n = g.vertices_size();
7            let mut size = 1;
8            let mut ok = true;
9            for a in g.adjacencies(u) {
10                if a.to != p {
11                    let (s, c) = dfs(g, a.to, u);
12                    if c != !0 {
13                        return (0, c);
14                    }
15                    ok &= s * 2 <= n;
16                    size += s;
17                }
18            }
19            ok &= (n - size) * 2 <= n;
20            (size, if ok { u } else { !0 })
21        }
22        dfs(self, 0, !0).1
23    }
24}