// ---------- 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 } } // ---------- end Centroid Decomposition ---------- // ---------- begin SegmentTree Range update Point query ---------- mod segment_tree { pub struct RUPQ { n: usize, b: usize, a: Vec, id: T, op: F, } impl T> RUPQ { pub fn new(n: usize, id: T, op: F) -> RUPQ { let mut k = 0; while (1 << k) < n { k += 1; } RUPQ { n: 1 << k, b: k, a: vec![id; 2 << k], id: id, op: op, } } fn down(&mut self, x: usize) { let k = x + self.n; let a = &mut self.a; for i in (1..(self.b + 1)).rev() { let y = k >> i; a[2 * y] = (self.op)(a[2 * y], a[y]); a[2 * y + 1] = (self.op)(a[2 * y + 1], a[y]); a[y] = self.id; } } pub fn update(&mut self, mut l: usize, mut r: usize, v: T) { self.down(l); self.down(r - 1); l += self.n; r += self.n; let a = &mut self.a; while l < r { if (l & 1) == 1 { a[l] = (self.op)(a[l], v); l += 1; } if (r & 1) == 1 { r -= 1; a[r] = (self.op)(a[r], v); } l >>= 1; r >>= 1; } } pub fn find(&mut self, mut x: usize) -> T { x += self.n; let mut y = self.a[x]; x >>= 1; while x > 0 { y = (self.op)(y, self.a[x]); x >>= 1; } y } } } // ---------- end SegmentTree Range update Point query ---------- //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 memo = vec![]; let mut max_rank = 0; 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 stack = vec![(v, v)]; while let Some((v, p)) = stack.pop() { 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)); } } } } if update { memo.push(dp); max_rank = rank; } else { break; } } max_rank += 1; let mut add = vec![]; let mut sub = vec![]; for i in 0..n { let r = cent.rank(i); let size = 1 << (max_rank - r); add.push(segment_tree::RUPQ::new(size, 0, |a, b| a + b)); sub.push(segment_tree::RUPQ::new(size, 0, |a, b| a + b)); } 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].find(d); } for (&g, memo) in belong.iter().skip(1).zip(memo.iter()) { let d = memo[x]; ans -= sub[g].find(d); } writeln!(out, "{}", ans).ok(); for (i, (&g, memo)) in belong.iter().zip(memo.iter()).enumerate() { let d = memo[x]; if y >= d { let r = std::cmp::min(y - d + 1, 1 << (max_rank - i)); add[g].update(0, r, z); } } for (i, (&g, memo)) in belong.iter().skip(1).zip(memo.iter()).enumerate() { let d = memo[x]; if y >= d { let r = std::cmp::min(y - d + 1, 1 << (max_rank - i - 1)); sub[g].update(0, r, z); } } } } fn main() { run(); }