verify/AtCoder/abc294g/src/main.rs

• View this file on GitHub
• Last update: 2025-03-09 01:10:53+09:00
• Link: https://atcoder.jp/contests/abc294/tasks/abc294_g

Depends on

• crates/data_structure/fenwick_tree/src/lib.rs
• crates/tree/hld/src/lib.rs

Code

// https://atcoder.jp/contests/abc294/tasks/abc294_g

use fenwick_tree::FenwickTree;
use hld::{Path, HLD};
use proconio::{fastout, input, marker::Usize1};

#[fastout]
fn main() {
    input! {
        n: usize,
        u_v_w: [(Usize1, Usize1, i64); n - 1],
        q: usize,
    }
    let mut graph = vec![vec![]; n];
    for &(u, v, _) in &u_v_w {
        graph[u].push(v);
        graph[v].push(u);
    }
    let hld = HLD::new(graph, 0);
    let edge_hld_id = {
        let mut ret = vec![0; n - 1];
        for i in 0..n - 1 {
            let (u, v, _) = u_v_w[i];
            if hld.parent[u] == v {
                ret[i] = hld.hld_in[u];
            } else {
                ret[i] = hld.hld_in[v];
            }
        }
        ret
    };
    let mut ft = FenwickTree::new(n, 0);
    for i in 0..n - 1 {
        let w = u_v_w[i].2;
        let id = edge_hld_id[i];
        ft.add(id, w);
    }
    for _ in 0..q {
        input! { t: usize }
        if t == 1 {
            input! {
                i: Usize1,
                w: i64,
            }
            let id = edge_hld_id[i];
            ft.set(id, w);
        } else {
            input! {
                u: Usize1,
                v: Usize1,
            }
            let mut ans = 0;
            for path in hld.path(u, v, false) {
                match path {
                    Path::Ascending(l, r) | Path::Descending(l, r) => {
                        ans += ft.sum(l..r);
                    }
                }
            }
            println!("{}", ans);
        }
    }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.9/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.9/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page