Skip to main content

UndirectedSparseGraph

competitive::graph::sparse_graph

Type Alias UndirectedSparseGraph 

Source 
pub type UndirectedSparseGraph = SparseGraph<UndirectedEdge>;

Aliased Type§

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

Fields§

§vsize: usize§start: Vec<usize>§elist: Vec<Adjacency>§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/centroid_decomposition.rs (lines 374-399)
363    pub fn distance_frequencies(&self) -> Vec<u64> {
364        let n = self.vertices_size();
365        let mut table = vec![0u64; n];
366        if n == 0 {
367            return table;
368        }
369        table[0] = n as u64;
370        if n == 1 {
371            return table;
372        }
373        table[1] = (n * 2 - 2) as u64;
374        self.centroid_decomposition(|parents, vs, lsize, _rsize| {
375            let n = vs.len();
376            let mut dist = vec![0usize; n];
377            for i in 1..n {
378                dist[i] = dist[parents[i]] + 1;
379            }
380            let d_max = dist.iter().max().cloned().unwrap_or_default();
381            let mut f = vec![0u64; d_max + 1];
382            let mut g = vec![0u64; d_max + 1];
383            for i in 1..=lsize {
384                f[dist[i]] += 1;
385            }
386            for i in lsize + 1..n {
387                g[dist[i]] += 1;
388            }
389            while f.last().is_some_and(|&x| x == 0) {
390                f.pop();
391            }
392            while g.last().is_some_and(|&x| x == 0) {
393                g.pop();
394            }
395            let h = U64Convolve::convolve(f, g);
396            for (i, &x) in h.iter().enumerate() {
397                table[i] += x * 2;
398            }
399        });
400        table
401    }
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 20)
16pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(cq.len() + 1);
22
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { v, l, r, x } => {
27                cq.for_each_contour_range(v, l, r, |start, end| {
28                    bit.update(start, x);
29                    bit.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, |i| ans += bit.accumulate(i));
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}
More examples
Hide additional examples
crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs (line 20)
16pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut raw = vec![0; cq.len()];
22    for (v, &x) in a.iter().enumerate() {
23        cq.for_each_index(v, |i| raw[i] += x);
24    }
25    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&raw);
26    for _ in 0..q {
27        scan!(scanner, query: Query);
28        match query {
29            Query::Add { p, x } => {
30                a[p] += x;
31                cq.for_each_index(p, |i| bit.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, |start, end| {
36                    ans += bit.fold(start, end);
37                });
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}
Source

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

Examples found in repository?
crates/library_checker/src/tree/frequency_table_of_tree_distance.rs (line 10)
6pub fn frequency_table_of_tree_distance(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, (g, _): @TreeGraphScanner::<usize>::new(n));
10    let freqs = g.distance_frequencies();
11    iter_print!(writer, @it freqs[1..].iter().map(|&f| f / 2));
12}
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.adjacencies(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>

Examples found in repository?
crates/competitive/src/tree/euler_tour.rs (line 192)
191    pub fn lca(&self, root: usize) -> LowestCommonAncestor {
192        let depth = self.tree_depth(root);
193        let mut trace = Vec::with_capacity(2 * self.vertices_size() - 1);
194        let mut depth_trace = Vec::with_capacity(2 * self.vertices_size() - 1);
195        let euler_tour = self.full_euler_tour_builder(root).build_with_trace(|u| {
196            trace.push(u);
197            depth_trace.push(depth[u]);
198        });
199        let rmq = RangeMinimumQuery::new(depth_trace);
200        LowestCommonAncestor {
201            euler_tour,
202            trace,
203            rmq,
204        }
205    }
More examples
Hide additional examples
crates/library_checker/src/tree/jump_on_tree.rs (line 34)
29pub fn jump_on_tree_batch(reader: impl Read, mut writer: impl Write) {
30    let s = read_all_unchecked(reader);
31    let mut scanner = Scanner::new(&s);
32    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize)]);
33    let lca = g.lca(0);
34    let depth = g.tree_depth(0);
35    let results = g.level_ancestor_batch(
36        0,
37        queries.take(q).map(|(s, t, i)| {
38            let l = lca.lca(s, t);
39            let ds = (depth[s] - depth[l]) as usize;
40            let dt = (depth[t] - depth[l]) as usize;
41            if i <= ds {
42                (s, i)
43            } else if i <= ds + dt {
44                (t, ds + dt - i)
45            } else {
46                (0, n)
47            }
48        }),
49    );
50    iter_print!(writer, @lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
51}
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.adjacencies(u).filter(|a| a.to != p) {
33            let nd = M::operate(&d, &weight(a.id));
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 10)
6pub fn grl_5_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, (graph, w): @TreeGraphScanner::<usize, u64>::new(n));
10    let d = graph.weighted_tree_depth::<AdditiveOperation<_>, _>(0, |eid| w[eid]);
11    let r = (0..n).max_by_key(|&u| d[u]).unwrap();
12    let ans = graph
13        .weighted_tree_depth::<AdditiveOperation<_>, _>(r, |eid| w[eid])
14        .into_iter()
15        .max()
16        .unwrap();
17    writeln!(writer, "{}", ans).ok();
18}
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.adjacencies(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 subtree_euler_tour_builder<'a>( &'a self, root: usize, ) -> EulerTourBuilder<'a, First>

Examples found in repository?
crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 21)
15pub fn vertex_add_subtree_sum(reader: impl Read, mut writer: impl Write) {
16    let s = read_all_unchecked(reader);
17    let mut scanner = Scanner::new(&s);
18    scan!(scanner, n, q, a: [u64; n], p: [usize]);
19    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
20    let tree = UndirectedSparseGraph::from_edges(n, edges);
21    let (et, b) = tree.subtree_euler_tour_builder(0).build_with_rearrange(&a);
22    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { u, x } => {
27                et.update(u, x, |k, x| seg.update(k, x));
28            }
29            Query::Sum { u } => {
30                writeln!(writer, "{}", et.fold(u, |r| seg.fold(r))).ok();
31            }
32        }
33    }
34}
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 26)
16pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, c: [SizedCollect<usize>]);
20    let edges = c
21        .take(n)
22        .enumerate()
23        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
24        .collect();
25    let graph = UndirectedSparseGraph::from_edges(n, edges);
26    let et = graph.path_euler_tour_builder(0).build();
27    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);
28
29    scan!(scanner, q);
30    for _ in 0..q {
31        scan!(scanner, query: Query);
32        match query {
33            Query::Add { v, w } => {
34                et.update(v, w, -w, |k, x| bit.update(k, x));
35            }
36            Query::Get { u } => {
37                let ans = et.fold(u, |k| bit.accumulate(k));
38                writeln!(writer, "{}", ans).ok();
39            }
40        }
41    }
42}
Source

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

Examples found in repository?
crates/competitive/src/tree/euler_tour.rs (line 195)
191    pub fn lca(&self, root: usize) -> LowestCommonAncestor {
192        let depth = self.tree_depth(root);
193        let mut trace = Vec::with_capacity(2 * self.vertices_size() - 1);
194        let mut depth_trace = Vec::with_capacity(2 * self.vertices_size() - 1);
195        let euler_tour = self.full_euler_tour_builder(root).build_with_trace(|u| {
196            trace.push(u);
197            depth_trace.push(depth[u]);
198        });
199        let rmq = RangeMinimumQuery::new(depth_trace);
200        LowestCommonAncestor {
201            euler_tour,
202            trace,
203            rmq,
204        }
205    }
Source

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

Examples found in repository?
crates/library_checker/src/tree/lca.rs (line 12)
6pub fn lca_euler_tour(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, p: [usize]);
10    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
11    let tree = UndirectedSparseGraph::from_edges(n, edges);
12    let lca = tree.lca(0);
13    for (u, v) in scanner.iter::<(usize, usize)>().take(q) {
14        writeln!(writer, "{}", lca.lca(u, v)).ok();
15    }
16}
More examples
Hide additional examples
crates/aizu_online_judge/src/grl/grl_5_c.rs (line 16)
6pub fn grl_5_c(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, c: [SizedCollect<usize>]);
10    let edges = c
11        .take(n)
12        .enumerate()
13        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
14        .collect();
15    let tree = UndirectedSparseGraph::from_edges(n, edges);
16    let lca = tree.lca(0);
17    scan!(scanner, q, uv: [(usize, usize)]);
18    for (u, v) in uv.take(q) {
19        writeln!(writer, "{}", lca.lca(u, v)).ok();
20    }
21}
crates/library_checker/src/tree/jump_on_tree.rs (line 11)
6pub fn jump_on_tree(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
10    let la = g.level_ancestor(0);
11    let lca = g.lca(0);
12    for _ in 0..q {
13        scan!(scanner, s, t, i);
14        let l = lca.lca(s, t);
15        let ds = la.depth(s) - la.depth(l);
16        let dt = la.depth(t) - la.depth(l);
17        let ans = if i <= ds {
18            la.la(s, i)
19        } else if i <= ds + dt {
20            la.la(t, ds + dt - i)
21        } else {
22            None
23        };
24        writeln!(writer, "{}", ans.unwrap_or(!0) as isize).ok();
25    }
26}
27
28#[verify::library_checker("jump_on_tree")]
29pub fn jump_on_tree_batch(reader: impl Read, mut writer: impl Write) {
30    let s = read_all_unchecked(reader);
31    let mut scanner = Scanner::new(&s);
32    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize)]);
33    let lca = g.lca(0);
34    let depth = g.tree_depth(0);
35    let results = g.level_ancestor_batch(
36        0,
37        queries.take(q).map(|(s, t, i)| {
38            let l = lca.lca(s, t);
39            let ds = (depth[s] - depth[l]) as usize;
40            let dt = (depth[t] - depth[l]) as usize;
41            if i <= ds {
42                (s, i)
43            } else if i <= ds + dt {
44                (t, ds + dt - i)
45            } else {
46                (0, n)
47            }
48        }),
49    );
50    iter_print!(writer, @lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
51}
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 10)
6pub fn jump_on_tree(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
10    let la = g.level_ancestor(0);
11    let lca = g.lca(0);
12    for _ in 0..q {
13        scan!(scanner, s, t, i);
14        let l = lca.lca(s, t);
15        let ds = la.depth(s) - la.depth(l);
16        let dt = la.depth(t) - la.depth(l);
17        let ans = if i <= ds {
18            la.la(s, i)
19        } else if i <= ds + dt {
20            la.la(t, ds + dt - i)
21        } else {
22            None
23        };
24        writeln!(writer, "{}", ans.unwrap_or(!0) as isize).ok();
25    }
26}
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 35-49)
29pub fn jump_on_tree_batch(reader: impl Read, mut writer: impl Write) {
30    let s = read_all_unchecked(reader);
31    let mut scanner = Scanner::new(&s);
32    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize)]);
33    let lca = g.lca(0);
34    let depth = g.tree_depth(0);
35    let results = g.level_ancestor_batch(
36        0,
37        queries.take(q).map(|(s, t, i)| {
38            let l = lca.lca(s, t);
39            let ds = (depth[s] - depth[l]) as usize;
40            let dt = (depth[t] - depth[l]) as usize;
41            if i <= ds {
42                (s, i)
43            } else if i <= ds + dt {
44                (t, ds + dt - i)
45            } else {
46                (0, n)
47            }
48        }),
49    );
50    iter_print!(writer, @lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
51}
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 117)
106pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, mut writer: impl Write) {
107    let s = read_all_unchecked(reader);
108    let mut scanner = Scanner::new(&s);
109    scan!(
110        scanner,
111        n,
112        q,
113        value: [MInt; n],
114        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
115    );
116
117    let top_tree = graph.static_top_tree(0);
118    let mut dp = top_tree.dp::<Dp>(value, edges);
119
120    for _ in 0..q {
121        scan!(scanner, query: Query);
122        match query {
123            Query::SetVertex { v, x } => {
124                dp.set_vertex(v, x);
125                writeln!(writer, "{}", dp.fold_all().sum).ok();
126            }
127            Query::SetEdge { e, a, b } => {
128                dp.set_edge(e, (a, b));
129                writeln!(writer, "{}", dp.fold_all().sum).ok();
130            }
131        }
132    }
133}
More examples
Hide additional examples
crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 151)
140pub fn point_set_tree_path_composite_sum(reader: impl Read, mut writer: impl Write) {
141    let s = read_all_unchecked(reader);
142    let mut scanner = Scanner::new(&s);
143    scan!(
144        scanner,
145        n,
146        q,
147        value: [MInt; n],
148        (graph, edges): @TreeGraphScanner::<usize, (MInt, MInt)>::new(n)
149    );
150
151    let top_tree = graph.static_top_tree(0);
152    let mut dp = top_tree.dp::<Dp>(value, edges);
153
154    for _ in 0..q {
155        scan!(scanner, query: Query);
156        match query {
157            Query::SetVertex { v, x, r } => {
158                dp.set_vertex(v, x);
159                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
160            }
161            Query::SetEdge { e, a, b, r } => {
162                dp.set_edge(e, (a, b));
163                writeln!(writer, "{}", dp.fold_path(r).reverse.sum).ok();
164            }
165        }
166    }
167}
Source§

impl UndirectedSparseGraph

Source

pub fn tree_center(&self) -> TreeCenter

tree center

Examples found in repository?
crates/competitive/src/tree/tree_hash.rs (line 51)
50    pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64 {
51        match g.tree_center() {
52            TreeCenter::One(u) => self.hash_rec(g, u, !0, 0),
53            TreeCenter::Two(u, v) => {
54                Self::mersenne_mul_mod(self.hash_rooted(g, u, v), self.hash_rooted(g, v, u))
55            }
56        }
57    }
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),