// ---------- begin Centroid Decomposition ---------- struct CentroidDecomposition { graph: Vec>, next: Vec<(usize, usize)>, } #[allow(dead_code)] impl CentroidDecomposition { fn new(n: usize) -> Self { CentroidDecomposition { graph: vec![vec![]; n], next: vec![], } } fn add_edge(&mut self, a: usize, b: usize) { self.graph[a].push(b); self.graph[b].push(a); } fn build(&mut self) { let graph = &self.graph; let next = &mut self.next; let n = graph.len(); next.clear(); next.resize(n, (n, n)); assert!( graph.iter().fold(0, |s, a| s + a.len()) == 2 * n - 2, "graph is not tree" ); let mut dfs = vec![(0, 0, n)]; let mut used = vec![false; n]; let mut size = vec![0; n]; let mut stack = vec![]; let mut q = vec![]; while let Some((v, rank, g)) = dfs.pop() { size[v] = 0; stack.push((v, v)); q.clear(); while let Some((v, p)) = stack.pop() { q.push(v); for &u in graph[v].iter() { size[u] = 0; if u != p && !used[u] { stack.push((u, v)); } } } for &v in q.iter().rev() { size[v] = 1; for &u in graph[v].iter() { size[v] += size[u]; } } let mut parent = v; let mut r = v; loop { let mut max = (0, 0); for &u in graph[r].iter() { if u != parent && !used[u] { max = std::cmp::max(max, (size[u], u)); } } if 2 * max.0 <= size[v] { break; } parent = r; r = max.1; } used[r] = true; next[r] = (rank, g); for &v in graph[r].iter() { if !used[v] { dfs.push((v, rank + 1, r)); } } } } fn belong(&self, v: usize) -> Vec { let mut ans = vec![]; let mut v = v; while v < self.graph.len() { ans.push(v); v = self.next[v].1; } ans } fn rank(&self, v: usize) -> usize { self.next[v].0 } fn parent(&self, v: usize) -> usize { assert!(self.next[v].0 > 0); self.next[v].1 } } // ---------- end Centroid Decomposition ---------- // ---------- begin fenwick tree ---------- #[allow(dead_code)] mod fenwick { type T = i64; const ZERO: T = 0; pub struct Tree { a: Box<[T]>, } impl Tree { pub fn new(n: usize) -> Tree { Tree { a: vec![ZERO; n + 1].into_boxed_slice(), } } pub fn size(&self) -> usize { self.a.len() - 1 } pub fn add(&mut self, mut x: usize, v: T) { assert!(x > 0); while let Some(a) = self.a.get_mut(x) { *a += v; x += x & (!x + 1); } } pub fn sum(&self, mut x: usize) -> T { assert!(x < self.a.len()); let mut res = ZERO; while x > 0 { res += self.a[x]; x -= x & (!x + 1); } res } pub fn search(&self, s: T) -> usize { debug_assert!(self.sum(self.a.len() - 1) >= s); let mut k = 1; while 2 * k < self.a.len() { k *= 2; } let mut x = 0; let mut w = ZERO; while k > 0 { self.a.get(x + k).map(|a| { if w + *a < s { w += *a; x += k; } }); k >>= 1; } x + 1 } } } // ---------- end fenwick tree ---------- //https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // use std::io::Write; fn run() { input! { n: usize, q: usize, e: [(usize1, usize1); n - 1], ask: [(usize1, usize, i64); q], } let mut cent = CentroidDecomposition::new(n); for (a, b) in e { cent.add_edge(a, b); } cent.build(); let mut size = vec![0; n]; let mut memo = vec![]; for rank in 0.. { let mut update = false; let mut dp = vec![std::usize::MAX; n]; for v in 0..n { if cent.rank(v) != rank { continue; } update = true; dp[v] = 0; let mut cnt = 0; let mut stack = vec![(v, v)]; while let Some((v, p)) = stack.pop() { cnt += 1; let d = dp[v] + 1; for &u in cent.graph[v].iter() { if u != p && cent.rank(u) > rank { dp[u] = d; stack.push((u, v)); } } } size[v] = cnt; } if update { memo.push(dp); } else { break; } } let mut add = vec![]; let mut sub = vec![]; for i in 0..n { add.push(fenwick::Tree::new(size[i])); if cent.rank(i) > 0 { let p = cent.parent(i); sub.push(fenwick::Tree::new(size[p])); } else { sub.push(fenwick::Tree::new(1)); } } let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); for (x, y, z) in ask { let mut ans = 0; let mut belong = cent.belong(x); belong.reverse(); for (&g, memo) in belong.iter().zip(memo.iter()) { let d = memo[x]; ans += add[g].sum(d + 1); } for (&g, memo) in belong.iter().skip(1).zip(memo.iter()) { let d = memo[x]; ans -= sub[g].sum(d + 1); } writeln!(out, "{}", ans).ok(); for (&g, memo) in belong.iter().zip(memo.iter()) { let d = memo[x]; if y >= d { let r = std::cmp::min(y - d + 1, add[g].size()); add[g].add(1, z); add[g].add(r + 1, -z); } } for (&g, memo) in belong.iter().skip(1).zip(memo.iter()) { let d = memo[x]; if y >= d { let r = std::cmp::min(y - d + 1, sub[g].size()); sub[g].add(1, z); sub[g].add(r + 1, -z); } } } } fn main() { run(); }