Skip to main content

UndirectedSparseGraph

competitive::graph

Type Alias UndirectedSparseGraph 

Source 
pub type UndirectedSparseGraph = SparseGraph<UndirectedEdge>;

Aliased Type§

pub struct UndirectedSparseGraph {
    vsize: usize,
    start: Vec<usize>,
    neighbors: Vec<Neighbor<usize, usize>>,
    pub edges: Vec<(usize, usize)>,
    _marker: PhantomData<fn() -> UndirectedEdge>,
}

Fields§

§vsize: usize§start: Vec<usize>§neighbors: Vec<Neighbor<usize, usize>>§edges: Vec<(usize, usize)>§_marker: PhantomData<fn() -> UndirectedEdge>

Implementations§

Source§

impl UndirectedSparseGraph

Source

pub fn to_graphvis<N, NA, E, EA>(&self, node_attr: N, edge_attr: E) -> String
where N: Fn(usize) -> NA, E: Fn(usize) -> EA, NA: Display, EA: Display,

Source§

impl UndirectedSparseGraph

Source

pub fn centroid_decomposition( &self, f: impl FnMut(&[usize], &[usize], usize, usize), )

1/3 centroid decomposition

  • f: (parents: &usize, vs: &usize, lsize: usize, rsize: usize)
  • 0: root, 1..=lsize: left subtree, lsize+1..=lsize+rsize: right subtree
Examples found in repository?
crates/competitive/src/tree/distance_frequencies.rs (lines 15-40)
4    pub fn distance_frequencies(&self) -> Vec<u64> {
5        let n = self.vertices_size();
6        let mut table = vec![0u64; n];
7        if n == 0 {
8            return table;
9        }
10        table[0] = n as u64;
11        if n == 1 {
12            return table;
13        }
14        table[1] = (n * 2 - 2) as u64;
15        self.centroid_decomposition(|parents, vs, lsize, _rsize| {
16            let n = vs.len();
17            let mut dist = vec![0usize; n];
18            for i in 1..n {
19                dist[i] = dist[parents[i]] + 1;
20            }
21            let d_max = dist.iter().max().cloned().unwrap_or_default();
22            let mut f = vec![0u64; d_max + 1];
23            let mut g = vec![0u64; d_max + 1];
24            for i in 1..=lsize {
25                f[dist[i]] += 1;
26            }
27            for i in lsize + 1..n {
28                g[dist[i]] += 1;
29            }
30            while f.last().is_some_and(|&x| x == 0) {
31                f.pop();
32            }
33            while g.last().is_some_and(|&x| x == 0) {
34                g.pop();
35            }
36            let h = U64Convolve::convolve(f, g);
37            for (i, &x) in h.iter().enumerate() {
38                table[i] += x * 2;
39            }
40        });
41        table
42    }
Source

pub fn contour_query_range(&self) -> ContourQueryRange

Examples found in repository?
crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (line 17)
14pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
17    let cq = graph.contour_query_range();
18    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = cq
19        .component_sizes()
20        .map(|n| BinaryIndexedTree::new(n + 1))
21        .collect();
22
23    for _ in 0..q {
24        sc!(query: Query);
25        match query {
26            Query::Add { v, l, r, x } => {
27                cq.for_each_contour_range(v, l, r, |c, start, end| {
28                    bits[c].update(start, x);
29                    bits[c].update(end, -x);
30                });
31                if l == 0 && 0 < r {
32                    a[v] += x;
33                }
34            }
35            Query::Get { v } => {
36                let mut ans = a[v];
37                cq.for_each_index(v, |c, i| ans += bits[c].accumulate(i));
38                pp!(ans);
39            }
40        }
41    }
42}
More examples
Hide additional examples
crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs (line 17)
14pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
17    let cq = graph.contour_query_range();
18    let mut raw: Vec<_> = cq.component_sizes().map(|n| vec![0; n]).collect();
19    for (v, &x) in a.iter().enumerate() {
20        cq.for_each_index(v, |c, i| raw[c][i] += x);
21    }
22    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = raw
23        .into_iter()
24        .map(|values| BinaryIndexedTree::from_slice(&values))
25        .collect();
26    for _ in 0..q {
27        sc!(query: Query);
28        match query {
29            Query::Add { p, x } => {
30                a[p] += x;
31                cq.for_each_index(p, |c, i| bits[c].update(i, x));
32            }
33            Query::Sum { v, l, r } => {
34                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
35                cq.for_each_contour_range(v, l, r, |c, start, end| {
36                    ans += bits[c].fold_abelian(start, end);
37                });
38                pp!(ans);
39            }
40        }
41    }
42}
Source§

impl UndirectedSparseGraph

Source

fn depth_dfs(&self, u: usize, p: usize, d: u64, depth: &mut Vec<u64>)

Examples found in repository?
crates/competitive/src/tree/depth.rs (line 9)
6    fn depth_dfs(&self, u: usize, p: usize, d: u64, depth: &mut Vec<u64>) {
7        depth[u] = d;
8        for a in self.neighbors(u).filter(|a| a.to != p) {
9            self.depth_dfs(a.to, u, d + 1, depth);
10        }
11    }
12    pub fn tree_depth(&self, root: usize) -> Vec<u64> {
13        let mut depth = vec![0; self.vertices_size()];
14        self.depth_dfs(root, self.vertices_size(), 0, &mut depth);
15        depth
16    }
Source

pub fn tree_depth(&self, root: usize) -> Vec<u64>

Source§

impl UndirectedSparseGraph

Source

fn weighted_depth_dfs<M, F>( &self, u: usize, p: usize, d: M::T, depth: &mut Vec<M::T>, weight: &F, )
where M: Monoid, F: Fn(usize) -> M::T,

Examples found in repository?
crates/competitive/src/tree/depth.rs (line 34)
21    fn weighted_depth_dfs<M, F>(
22        &self,
23        u: usize,
24        p: usize,
25        d: M::T,
26        depth: &mut Vec<M::T>,
27        weight: &F,
28    ) where
29        M: Monoid,
30        F: Fn(usize) -> M::T,
31    {
32        for a in self.neighbors(u).filter(|a| a.to != p) {
33            let nd = M::operate(&d, &weight(a.label));
34            self.weighted_depth_dfs::<M, _>(a.to, u, nd, depth, weight);
35        }
36        depth[u] = d;
37    }
38    pub fn weighted_tree_depth<M: Monoid, F: Fn(usize) -> M::T>(
39        &self,
40        root: usize,
41        weight: F,
42    ) -> Vec<M::T> {
43        let mut depth = vec![M::unit(); self.vertices_size()];
44        self.weighted_depth_dfs::<M, _>(root, usize::MAX, M::unit(), &mut depth, &weight);
45        depth
46    }
Source

pub fn weighted_tree_depth<M: Monoid, F: Fn(usize) -> M::T>( &self, root: usize, weight: F, ) -> Vec<M::T>

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_5_a.rs (line 8)
5pub fn grl_5_a(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, (graph, w): @TreeGraphScanner::<usize, u64>::new(n));
8    let d = graph.weighted_tree_depth::<AdditiveOperation<_>, _>(0, |eid| w[eid]);
9    let r = (0..n).max_by_key(|&u| d[u]).unwrap();
10    let ans = graph
11        .weighted_tree_depth::<AdditiveOperation<_>, _>(r, |eid| w[eid])
12        .into_iter()
13        .max()
14        .unwrap();
15    pp!(ans);
16}
Source§

impl UndirectedSparseGraph

Source

fn size_dfs(&self, u: usize, p: usize, size: &mut Vec<u64>)

Examples found in repository?
crates/competitive/src/tree/depth.rs (line 54)
51    fn size_dfs(&self, u: usize, p: usize, size: &mut Vec<u64>) {
52        size[u] = 1;
53        for a in self.neighbors(u).filter(|a| a.to != p) {
54            self.size_dfs(a.to, u, size);
55            size[u] += size[a.to];
56        }
57    }
58    pub fn tree_size(&self, root: usize) -> Vec<u64> {
59        let mut size = vec![0; self.vertices_size()];
60        self.size_dfs(root, usize::MAX, &mut size);
61        size
62    }
Source

pub fn tree_size(&self, root: usize) -> Vec<u64>

Source§

impl UndirectedSparseGraph

Source

pub fn distance_frequencies(&self) -> Vec<u64>

Examples found in repository?
crates/library_checker/src/tree/frequency_table_of_tree_distance.rs (line 8)
5pub fn frequency_table_of_tree_distance(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, (g, _): @TreeGraphScanner::<usize>::new(n));
8    let freqs = g.distance_frequencies();
9    pp!(@it freqs[1..].iter().map(|&f| f / 2));
10}
Source§

impl UndirectedSparseGraph

Source

pub fn subtree_euler_tour_builder<'a>( &'a self, root: usize, ) -> EulerTourBuilder<'a, First>

Source

pub fn path_euler_tour_builder<'a>( &'a self, root: usize, ) -> EulerTourBuilder<'a, FirstLast>

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_5_d.rs (line 23)
15pub fn grl_5_d(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, c: [SizedCollect<usize>; iter n]);
18    let edges = c
19        .enumerate()
20        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
21        .collect();
22    let graph = UndirectedSparseGraph::from_edges(n, edges);
23    let et = graph.path_euler_tour_builder(0).build();
24    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);
25
26    sc!(q);
27    for _ in 0..q {
28        sc!(query: Query);
29        match query {
30            Query::Add { v, w } => {
31                et.update(v, w, -w, |k, x| bit.update(k, x));
32            }
33            Query::Get { u } => {
34                let ans = et.fold(u, |k| bit.accumulate(k));
35                pp!(ans);
36            }
37        }
38    }
39}
Source

pub fn full_euler_tour_builder<'a>( &'a self, root: usize, ) -> EulerTourBuilder<'a, Visit>

Source

pub fn lca(&self, root: usize) -> LowestCommonAncestor

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_5_c.rs (line 13)
5pub fn grl_5_c(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, c: [SizedCollect<usize>; iter n]);
8    let edges = c
9        .enumerate()
10        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
11        .collect();
12    let tree = UndirectedSparseGraph::from_edges(n, edges);
13    let lca = tree.lca(0);
14    sc!(q, uv: [(usize, usize); iter q]);
15    for (u, v) in uv {
16        pp!(lca.lca(u, v));
17    }
18}
More examples
Hide additional examples
crates/library_checker/src/tree/jump_on_tree.rs (line 20)
16pub fn jump_on_tree_level_ancestor(reader: impl Read, writer: impl Write) {
17    prepare_io!(reader, writer);
18    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
19    let la = g.level_ancestor(0);
20    let lca = g.lca(0);
21    for _ in 0..q {
22        sc!(s, t, i);
23        let l = lca.lca(s, t);
24        let dl = la.depth(l);
25        let ds = la.depth(s) - dl;
26        let dt = la.depth(t) - dl;
27        let ans = if i <= ds {
28            la.la(s, i)
29        } else if i <= ds + dt {
30            la.la(t, ds + dt - i)
31        } else {
32            None
33        };
34        pp!(ans.unwrap_or(!0) as isize);
35    }
36}
37
38#[verify::library_checker("jump_on_tree")]
39pub fn jump_on_tree_level_ancestor_batch(reader: impl Read, writer: impl Write) {
40    prepare_io!(reader, writer);
41    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize); iter q]);
42    let lca = g.lca(0);
43    let results = g.level_ancestor_batch(
44        0,
45        queries.map(|(s, t, i)| {
46            let l = lca.lca(s, t);
47            let dl = lca.depth(l);
48            let ds = lca.depth(s) - dl;
49            let dt = lca.depth(t) - dl;
50            if i <= ds {
51                (s, i)
52            } else if i <= ds + dt {
53                (t, ds + dt - i)
54            } else {
55                (0, n)
56            }
57        }),
58    );
59    pp!(@lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
60}
Source§

impl UndirectedSparseGraph

Source

pub fn hld(&self, root: usize) -> HeavyLightDecomposition

Examples found in repository?
crates/library_checker/src/tree/jump_on_tree.rs (line 8)
5pub fn jump_on_tree(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
8    let hld = g.hld(0);
9    for _ in 0..q {
10        sc!(s, t, i);
11        pp!(hld.jump(s, t, i).unwrap_or(!0) as isize);
12    }
13}
More examples
Hide additional examples
crates/library_checker/src/tree/lca.rs (line 24)
19pub fn lca_hld(reader: impl Read, writer: impl Write) {
20    prepare_io!(reader, writer);
21    sc!(n, q, p: [usize; iter n - 1]);
22    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
23    let graph = UndirectedSparseGraph::from_edges(n, edges);
24    let hld = graph.hld(0);
25    for _ in 0..q {
26        sc!(u, v);
27        pp!(hld.lca(u, v));
28    }
29}
crates/library_checker/src/tree/vertex_set_path_composite.rs (line 17)
14pub fn vertex_set_path_composite(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, ab: [(M, M); n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
17    let hld = graph.hld(0);
18    let mut fold = hld.build_fold::<LinearOperation<_>>(&ab);
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Set { p, cd } => {
23                fold.set(p, cd);
24            }
25            Query::Apply { u, v, x } => {
26                let (a, b) = fold.fold_vertices(u, v);
27                pp!(a * x + b);
28            }
29        }
30    }
31}
crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 43)
38pub fn vertex_add_subtree_sum_hld(reader: impl Read, writer: impl Write) {
39    prepare_io!(reader, writer);
40    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
41    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
42    let tree = UndirectedSparseGraph::from_edges(n, edges);
43    let hld = tree.hld(0);
44    let mut b = vec![0; n];
45    for (v, x) in a.into_iter().enumerate() {
46        b[hld.index(v)] = x;
47    }
48    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
49    for _ in 0..q {
50        sc!(query: Query);
51        match query {
52            Query::Add { u, x } => seg.update(hld.index(u), x),
53            Query::Sum { u } => {
54                pp!(seg.fold(hld.subtree_range(u)));
55            }
56        }
57    }
58}
crates/aizu_online_judge/src/grl/grl_5_e.rs (line 23)
15pub fn grl_5_e(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, c: [SizedCollect<usize>; iter n]);
18    let edges = c
19        .enumerate()
20        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
21        .collect();
22    let graph = UndirectedSparseGraph::from_edges(n, edges);
23    let hld = graph.hld(0);
24    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_keys(std::iter::repeat_n(0u64, n));
25
26    sc!(q);
27    for _ in 0..q {
28        sc!(query: Query);
29        match query {
30            Query::Add { v, w } => {
31                hld.path_edges(0, v, |l, r| seg.update(l..r, w));
32            }
33            Query::Get { u } => {
34                let mut ans = 0;
35                hld.path_edges(0, u, |l, r| ans += seg.fold(l..r).0);
36                pp!(ans);
37            }
38        }
39    }
40}
Source§

impl UndirectedSparseGraph

Source

pub fn level_ancestor(&self, root: usize) -> LevelAncestor

Examples found in repository?
crates/library_checker/src/tree/jump_on_tree.rs (line 19)
16pub fn jump_on_tree_level_ancestor(reader: impl Read, writer: impl Write) {
17    prepare_io!(reader, writer);
18    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
19    let la = g.level_ancestor(0);
20    let lca = g.lca(0);
21    for _ in 0..q {
22        sc!(s, t, i);
23        let l = lca.lca(s, t);
24        let dl = la.depth(l);
25        let ds = la.depth(s) - dl;
26        let dt = la.depth(t) - dl;
27        let ans = if i <= ds {
28            la.la(s, i)
29        } else if i <= ds + dt {
30            la.la(t, ds + dt - i)
31        } else {
32            None
33        };
34        pp!(ans.unwrap_or(!0) as isize);
35    }
36}
More examples
Hide additional examples
crates/competitive/src/algorithm/doubling.rs (line 278)
183    pub fn new(size: usize, f: impl Fn(usize) -> (usize, M::T)) -> Self {
184        let (next, value): (Vec<_>, Vec<_>) = (0..size).map(f).unzip();
185
186        let mut indeg = vec![0usize; size];
187        for &to in &next {
188            indeg[to] += 1;
189        }
190        let mut in_cycle = vec![true; size];
191        let mut deq = VecDeque::new();
192        for (u, &deg) in indeg.iter().enumerate() {
193            if deg == 0 {
194                deq.push_back(u);
195            }
196        }
197        while let Some(u) = deq.pop_front() {
198            in_cycle[u] = false;
199            indeg[next[u]] -= 1;
200            if indeg[next[u]] == 0 {
201                deq.push_back(next[u]);
202            }
203        }
204
205        let mut cycle_id = vec![!0; size];
206        let mut cycle_pos = vec![!0; size];
207        let mut cycles = Vec::new();
208        for i in 0..size {
209            if in_cycle[i] && cycle_id[i] == !0 {
210                let mut cycle = Vec::new();
211                let mut u = i;
212                loop {
213                    cycle_id[u] = cycles.len();
214                    cycle_pos[u] = cycle.len();
215                    cycle.push(u);
216                    u = next[u];
217                    if u == i {
218                        break;
219                    }
220                }
221                cycles.push(cycle);
222            }
223        }
224
225        let mut rev = vec![Vec::new(); size];
226        for u in 0..size {
227            rev[next[u]].push(u);
228        }
229
230        let mut depth_to_cycle = vec![0usize; size];
231        let mut cycle_entry = vec![!0; size];
232        let mut prefix_up = Vec::with_capacity(size);
233        prefix_up.resize_with(size, M::unit);
234        let mut q = VecDeque::new();
235        for i in 0..size {
236            if in_cycle[i] {
237                cycle_entry[i] = i;
238                prefix_up[i] = M::operate(&value[i], &M::unit());
239                q.push_back(i);
240            }
241        }
242        while let Some(u) = q.pop_front() {
243            for &v in &rev[u] {
244                if in_cycle[v] || cycle_entry[v] != !0 {
245                    continue;
246                }
247                cycle_entry[v] = cycle_entry[u];
248                depth_to_cycle[v] = depth_to_cycle[u] + 1;
249                cycle_id[v] = cycle_id[u];
250                prefix_up[v] = M::operate(&value[v], &prefix_up[u]);
251                q.push_back(v);
252            }
253        }
254
255        let mut cycle_prefix = Vec::with_capacity(cycles.len());
256        for cycle in &cycles {
257            let len = cycle.len();
258            let mut pref = Vec::with_capacity(2 * len + 1);
259            pref.push(M::unit());
260            for i in 0..2 * len {
261                let v = cycle[i % len];
262                let next_val = M::operate(pref.last().unwrap(), &value[v]);
263                pref.push(next_val);
264            }
265            cycle_prefix.push(pref);
266        }
267
268        let root = size;
269        let mut edges = Vec::with_capacity(size);
270        for u in 0..size {
271            if in_cycle[u] {
272                edges.push((u, root));
273            } else {
274                edges.push((u, next[u]));
275            }
276        }
277        let graph = UndirectedSparseGraph::from_edges(size + 1, edges);
278        let la = graph.level_ancestor(root);
279
280        Self {
281            depth_to_cycle,
282            cycle_entry,
283            cycle_id,
284            cycle_pos,
285            cycles,
286            cycle_prefix,
287            prefix_up,
288            la,
289        }
290    }
Source

pub fn level_ancestor_batch( &self, root: usize, queries: impl IntoIterator<Item = (usize, usize)>, ) -> Vec<Option<usize>>

Examples found in repository?
crates/library_checker/src/tree/jump_on_tree.rs (lines 43-58)
39pub fn jump_on_tree_level_ancestor_batch(reader: impl Read, writer: impl Write) {
40    prepare_io!(reader, writer);
41    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize); iter q]);
42    let lca = g.lca(0);
43    let results = g.level_ancestor_batch(
44        0,
45        queries.map(|(s, t, i)| {
46            let l = lca.lca(s, t);
47            let dl = lca.depth(l);
48            let ds = lca.depth(s) - dl;
49            let dt = lca.depth(t) - dl;
50            if i <= ds {
51                (s, i)
52            } else if i <= ds + dt {
53                (t, ds + dt - i)
54            } else {
55                (0, n)
56            }
57        }),
58    );
59    pp!(@lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
60}
Source§

impl UndirectedSparseGraph

Source

pub fn static_top_tree(&self, root: usize) -> StaticTopTree

Examples found in repository?
crates/library_checker/src/tree/point_set_tree_path_composite_sum_fixed_root.rs (line 110)
103pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, writer: impl Write) {
104    prepare_io!(reader, writer);
105    sc!(n,
106        q,
107        value: [M; n],
108        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
109
110    let top_tree = graph.static_top_tree(0);
111    let mut dp = top_tree.dp::<Dp>(value, edges);
112
113    for _ in 0..q {
114        sc!(query: Query);
115        match query {
116            Query::SetVertex { v, x } => {
117                dp.set_vertex(v, x);
118                pp!(dp.fold_all().sum);
119            }
120            Query::SetEdge { e, a, b } => {
121                dp.set_edge(e, (a, b));
122                pp!(dp.fold_all().sum);
123            }
124        }
125    }
126}
More examples
Hide additional examples
crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 144)
137pub fn point_set_tree_path_composite_sum(reader: impl Read, writer: impl Write) {
138    prepare_io!(reader, writer);
139    sc!(n,
140        q,
141        value: [M; n],
142        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
143
144    let top_tree = graph.static_top_tree(0);
145    let mut dp = top_tree.dp::<Dp>(value, edges);
146
147    for _ in 0..q {
148        sc!(query: Query);
149        match query {
150            Query::SetVertex { v, x, r } => {
151                dp.set_vertex(v, x);
152                pp!(dp.fold_path(r).reverse.sum);
153            }
154            Query::SetEdge { e, a, b, r } => {
155                dp.set_edge(e, (a, b));
156                pp!(dp.fold_path(r).reverse.sum);
157            }
158        }
159    }
160}
Source§

impl UndirectedSparseGraph

Source

pub fn tree_center(&self) -> TreeCenter

tree center

Examples found in repository?
crates/competitive/src/tree/tree_hash.rs (line 55)
54    pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64 {
55        match g.tree_center() {
56            TreeCenter::One(u) => self.hash_rec(g, u, !0, 0),
57            TreeCenter::Two(u, v) => {
58                Self::mersenne_mul_mod(self.hash_rooted(g, u, v), self.hash_rooted(g, v, u))
59            }
60        }
61    }
Source§

impl UndirectedSparseGraph

Source

pub fn tree_centroid(&self) -> usize

Source§

impl UndirectedSparseGraph

Source

pub fn tree_dp_bottom_up<T, F>(&self, root: usize, dp: &mut [T], f: F)
where F: FnMut(&mut T, &T),

Source

pub fn tree_dp_top_down<T, F>(&self, root: usize, dp: &mut [T], f: F)
where F: FnMut(&mut T, &T),