use crate::segtree::Segtree; use proconio::input; use std::cmp::Reverse; use std::ops::Bound; fn main() { input! { n: usize, edges: [(usize, usize, i64); n - 1], q: usize, } let mut g = vec![Vec::new(); n]; for &(i, j, _) in &edges { g[i].push(j); g[j].push(i); } let mut stack = vec![0]; let mut parent = vec![usize::MAX; n]; let mut depth = vec![0; n]; parent[0] = 0; let mut size = vec![1; n]; while let Some(x) = stack.pop() { if x <= isize::MAX as usize { stack.push(!x); g[x].retain(|&y| y != parent[x]); for &y in &g[x] { if parent[y] != usize::MAX { continue; } parent[y] = x; depth[y] = depth[x] + 1; stack.push(y); } } else { let x = !x; g[x].sort_unstable_by_key(|&y| Reverse(size[y])); for &y in &g[x] { size[x] += size[y]; } } } let mut sorted = Vec::new(); let mut position = vec![usize::MAX; n]; let mut head = (0..n).collect::>(); let mut stack = vec![0]; while let Some(x) = stack.pop() { position[x] = sorted.len(); sorted.push(x); if let Some(&y) = g[x].first() { head[y] = head[x]; } stack.extend(g[x].iter().rev().copied()); } let mut original = Segtree::::from_len(n); let mut additional = Segtree::::from_len(n); for &(i, j, w) in &edges { let i = if parent[i] == j { i } else { j }; *original.entry(position[i]) = w; } for _ in 0..q { input! { com: u8, } match com { 1 => { input! { i: usize, x: i64, } let mut e = additional.entry(position[i]); e.additional += x; e.weighted += x * depth[i] as i64; } 2 => { input! { mut j: usize, } let mut ans = 0; let coeff = depth[j]; loop { if head[j] == 0 { let original = original.fold((Bound::Excluded(0), Bound::Included(position[j]))); let Value { additional, weighted, } = additional.fold(0..=position[j]); ans += additional * coeff as i64 - weighted + original; break; } let original = original.fold(position[head[j]]..=position[j]); let Value { additional, weighted, } = additional.fold(position[head[j]]..=position[j]); ans += additional * coeff as i64 - weighted + original; j = parent[head[j]]; } println!("{}", ans); } _ => unreachable!(), } } } enum O1 {} impl segtree::Op for O1 { type Value = i64; fn identity() -> Self::Value { 0 } fn op(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value { lhs + rhs } } #[derive(Clone, Copy)] struct Value { additional: i64, weighted: i64, } enum O2 {} impl segtree::Op for O2 { type Value = Value; fn identity() -> Self::Value { Value { additional: 0, weighted: 0, } } fn op(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value { Value { additional: lhs.additional + rhs.additional, weighted: lhs.weighted + rhs.weighted, } } } // segtree {{{ // https://ngtkana.github.io/ac-adapter-rs/segtree/index.html #[allow(dead_code)] mod segtree { use core::fmt; use std::collections::BTreeMap; use std::iter::FromIterator; use std::ops::Deref; use std::ops::DerefMut; use std::ops::Index; use std::ops::RangeBounds; pub trait Op { type Value; fn identity() -> Self::Value; fn op(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value; } pub struct Segtree { values: Vec, } impl Segtree { pub fn from_len(n: usize) -> Self where O::Value: Clone, { Self::new(&vec![O::identity(); n]) } pub fn new(values: &[O::Value]) -> Self where O::Value: Clone, { let values_ = values; let n = values.len(); let mut values = vec![O::identity(); 2 * n]; values[n..].clone_from_slice(values_); for i in (1..n).rev() { values[i] = O::op(&values[i * 2], &values[i * 2 + 1]); } Self { values } } pub fn fold>(&self, range: R) -> O::Value { let n = self.values.len() / 2; let (mut start, mut end) = open(range, n); assert!(start <= end && end <= n); start += n; end += n; let mut left = O::identity(); let mut right = O::identity(); while start < end { if start % 2 == 1 { left = O::op(&left, &self.values[start]); start += 1; } if end % 2 == 1 { end -= 1; right = O::op(&self.values[end], &right); } start /= 2; end /= 2; } O::op(&left, &right) } pub fn entry(&mut self, index: usize) -> Entry { let n = self.values.len() / 2; Entry { segtree: self, index: n + index, } } pub fn iter(&self) -> impl Iterator { self.values[self.values.len() / 2..].iter() } pub fn as_slice(&self) -> &[O::Value] { &self.values[self.values.len() / 2..] } } impl fmt::Debug for Segtree where O::Value: fmt::Debug, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_struct("Segtree") .field("values", &self.values) .finish() } } impl FromIterator for Segtree where O::Value: Clone, { fn from_iter>(iter: I) -> Self { Self::new(&iter.into_iter().collect::>()) } } impl Index for Segtree { type Output = O::Value; fn index(&self, index: usize) -> &Self::Output { &self.values[self.values.len() / 2 + index] } } pub struct Entry<'a, O: Op> { segtree: &'a mut Segtree, index: usize, } impl<'a, O: Op> Drop for Entry<'a, O> { fn drop(&mut self) { let mut index = self.index; while index != 0 { index /= 2; self.segtree.values[index] = O::op( &self.segtree.values[index * 2], &self.segtree.values[index * 2 + 1], ); } } } impl<'a, O: Op> Deref for Entry<'a, O> { type Target = O::Value; fn deref(&self) -> &Self::Target { &self.segtree.values[self.index] } } impl<'a, O: Op> DerefMut for Entry<'a, O> { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.segtree.values[self.index] } } impl<'a, O: Op> fmt::Debug for Entry<'a, O> where O::Value: fmt::Debug, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_struct("Entry").field("index", &self.index).finish() } } pub struct SparseSegtree { inner: Segtree, keys: Vec, } impl SparseSegtree { pub fn new(kv: &[(K, O::Value)]) -> Self where K: Clone, O::Value: Clone, { let mut keys = kv.iter().map(|(k, _)| k.clone()).collect::>(); keys.sort(); let values = kv.iter().map(|(_, v)| v.clone()).collect::>(); Self { inner: Segtree::new(&values), keys, } } pub fn fold>(&self, range: R) -> O::Value { let (start, end) = open_key(range, &self.keys); self.inner.fold(start..end) } pub fn entry(&mut self, key: &K) -> Entry<'_, O> { let index = self.keys.binary_search(key).unwrap() + self.keys.len(); Entry { segtree: &mut self.inner, index, } } pub fn keys(&self) -> &[K] { &self.keys } pub fn iter(&self) -> impl Iterator { self.keys.iter().zip(self.inner.as_slice()) } pub fn collect_map(&self) -> BTreeMap where K: Clone, O::Value: Clone, { self.keys .iter() .cloned() .zip(self.inner.iter().cloned()) .collect() } } impl fmt::Debug for SparseSegtree where K: fmt::Debug, O::Value: fmt::Debug, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_struct("SparseSegtree") .field("inner", &self.inner) .field("keys", &self.keys) .finish() } } impl FromIterator<(K, O::Value)> for SparseSegtree where K: Clone, O::Value: Clone, { fn from_iter>(iter: I) -> Self { Self::new(&iter.into_iter().collect::>()) } } impl Index for SparseSegtree { type Output = O::Value; fn index(&self, key: K) -> &Self::Output { &self.inner[self.keys.binary_search(&key).unwrap()] } } pub struct Sparse2dSegtree { segtrees: Vec>, keys: Vec, } impl Sparse2dSegtree where K: Ord + Clone, L: Ord + Clone, O::Value: Clone, { pub fn new(points: &[(K, L, O::Value)]) -> Self { let mut keys = points.iter().map(|(k, _, _)| k.clone()).collect::>(); keys.sort(); keys.dedup(); let mut lvs = vec![vec![]; keys.len() * 2]; for (k, l, v) in points { let mut i = keys.binary_search(k).unwrap(); i += keys.len(); while i != 0 { lvs[i].push((l.clone(), v.clone())); i /= 2; } } let segtrees = lvs .into_iter() .map(|lvs_| { let mut ls = lvs_.iter().map(|(l, _)| l).collect::>(); ls.sort(); ls.dedup(); let mut lvs = ls .iter() .map(|&l| (l.clone(), O::identity())) .collect::>(); for (l, v) in &lvs_ { let i = ls.binary_search(&l).unwrap(); lvs[i].1 = O::op(&lvs[i].1, v); } SparseSegtree::new(&lvs) }) .collect::>(); Self { segtrees, keys } } pub fn fold(&self, i: impl RangeBounds, j: impl RangeBounds + Clone) -> O::Value { let (mut i0, mut i1) = open_key(i, &self.keys); i0 += self.keys.len(); i1 += self.keys.len(); let mut left = O::identity(); let mut right = O::identity(); while i0 < i1 { if i0 % 2 == 1 { left = O::op(&left, &self.segtrees[i0].fold(j.clone())); i0 += 1; } if i1 % 2 == 1 { i1 -= 1; right = O::op(&self.segtrees[i1].fold(j.clone()), &right); } i0 /= 2; i1 /= 2; } O::op(&left, &right) } pub fn apply(&mut self, k: &K, l: &L, mut f: impl FnMut(&mut O::Value)) { let mut i = self.keys.binary_search(k).unwrap(); i += self.keys.len(); while i != 0 { f(&mut self.segtrees[i].entry(l)); i /= 2; } } pub fn iter(&self) -> impl Iterator { self.keys .iter() .zip(self.segtrees[self.keys.len()..].iter()) .flat_map(|(k, segtree)| segtree.iter().map(move |(l, v)| (k, l, v))) } pub fn collect_map(&self) -> BTreeMap<(K, L), O::Value> where K: Clone, L: Clone, O::Value: Clone, { self.keys .iter() .flat_map(|k| { self.segtrees[self.keys.len() + self.keys.binary_search(k).unwrap()] .iter() .map(move |(l, v)| ((k.clone(), l.clone()), v.clone())) }) .collect() } } impl fmt::Debug for Sparse2dSegtree where K: fmt::Debug, L: fmt::Debug, O::Value: fmt::Debug, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_struct("Sparse2dSegtree") .field("segtrees", &self.segtrees) .field("keys", &self.keys) .finish() } } impl FromIterator<(K, L, O::Value)> for Sparse2dSegtree where K: Ord + Clone, L: Ord + Clone, O::Value: Clone, { fn from_iter>(iter: I) -> Self { Self::new(&iter.into_iter().collect::>()) } } impl Index for Sparse2dSegtree { type Output = SparseSegtree; fn index(&self, i: K) -> &Self::Output { &self.segtrees[self.keys.binary_search(&i).unwrap() + self.keys.len()] } } impl Index<(K, L)> for Sparse2dSegtree { type Output = O::Value; fn index(&self, (i, j): (K, L)) -> &Self::Output { &self.segtrees[self.keys.binary_search(&i).unwrap() + self.keys.len()][j] } } pub struct Dense2dSegtree { values: Vec>, } impl Dense2dSegtree { pub fn new(values: &[Vec]) -> Self where O::Value: Clone, { let values_ = values; let h = values.len(); let w = values.get(0).map_or(0, Vec::len); let mut values = vec![vec![O::identity(); 2 * w]; 2 * h]; for (values, values_) in values[h..].iter_mut().zip(values_) { values[w..].clone_from_slice(values_); for j in (1..w).rev() { values[j] = O::op(&values[j * 2], &values[j * 2 + 1]); } } for i in (1..h).rev() { for j in 0..2 * w { values[i][j] = O::op(&values[i * 2][j], &values[i * 2 + 1][j]); } } Self { values } } pub fn fold(&self, i: impl RangeBounds, j: impl RangeBounds) -> O::Value { let h = self.values.len() / 2; let w = self.values.get(0).map_or(0, |v| v.len() / 2); let (mut i0, mut i1) = open(i, h); assert!(i0 <= i1 && i1 <= h); let (mut j0, mut j1) = open(j, w); assert!(j0 <= j1 && j1 <= w); i0 += h; i1 += h; j0 += w; j1 += w; let mut left = O::identity(); let mut right = O::identity(); while i0 < i1 { if i0 % 2 == 1 { let mut j0 = j0; let mut j1 = j1; while j0 < j1 { if j0 % 2 == 1 { left = O::op(&left, &self.values[i0][j0]); j0 += 1; } if j1 % 2 == 1 { j1 -= 1; right = O::op(&self.values[i0][j1], &right); } j0 /= 2; j1 /= 2; } i0 += 1; } if i1 % 2 == 1 { i1 -= 1; let mut j0 = j0; let mut j1 = j1; while j0 < j1 { if j0 % 2 == 1 { left = O::op(&left, &self.values[i1][j0]); j0 += 1; } if j1 % 2 == 1 { j1 -= 1; right = O::op(&self.values[i1][j1], &right); } j0 /= 2; j1 /= 2; } } i0 /= 2; i1 /= 2; } O::op(&left, &right) } pub fn entry(&mut self, i: usize, j: usize) -> Dense2dEntry { let h = self.values.len() / 2; let w = self.values.get(0).map_or(0, |v| v.len() / 2); Dense2dEntry { segtree: self, i: h + i, j: w + j, } } pub fn iter(&self) -> impl Iterator { self.values[self.values.len() / 2..] .iter() .map(|v| &v[v.len() / 2..]) } pub fn collect_vec(&self) -> Vec> where O::Value: Clone, { self.iter().map(<[_]>::to_vec).collect() } } impl fmt::Debug for Dense2dSegtree where O::Value: fmt::Debug, { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_struct("Dense2dSegtree") .field("values", &self.values) .finish() } } impl Index for Dense2dSegtree { type Output = [O::Value]; fn index(&self, index: usize) -> &Self::Output { &self.values[self.values.len() / 2 + index] } } pub struct Dense2dEntry<'a, O: Op> { segtree: &'a mut Dense2dSegtree, i: usize, j: usize, } impl<'a, O: Op> Drop for Dense2dEntry<'a, O> { fn drop(&mut self) { let mut i = self.i; let mut j = self.j / 2; while j != 0 { self.segtree.values[i][j] = O::op( &self.segtree.values[i][2 * j], &self.segtree.values[i][2 * j + 1], ); j /= 2; } i /= 2; while i != 0 { let mut j = self.j; while j != 0 { self.segtree.values[i][j] = O::op( &self.segtree.values[i * 2][j], &self.segtree.values[i * 2 + 1][j], ); j /= 2; } i /= 2; } } } impl<'a, O: Op> Deref for Dense2dEntry<'a, O> { type Target = O::Value; fn deref(&self) -> &Self::Target { &self.segtree.values[self.i][self.j] } } impl<'a, O: Op> DerefMut for Dense2dEntry<'a, O> { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.segtree.values[self.i][self.j] } } fn open>(bounds: B, n: usize) -> (usize, usize) { use std::ops::Bound; let start = match bounds.start_bound() { Bound::Unbounded => 0, Bound::Included(&x) => x, Bound::Excluded(&x) => x + 1, }; let end = match bounds.end_bound() { Bound::Unbounded => n, Bound::Included(&x) => x + 1, Bound::Excluded(&x) => x, }; (start, end) } fn open_key>(bounds: B, keys: &[K]) -> (usize, usize) { use std::ops::Bound; let start = match bounds.start_bound() { Bound::Unbounded => 0, Bound::Included(x) => match keys.binary_search(x) { Ok(i) | Err(i) => i, }, Bound::Excluded(x) => match keys.binary_search(x) { Ok(i) => i + 1, Err(i) => i, }, }; let end = match bounds.end_bound() { Bound::Unbounded => keys.len(), Bound::Included(x) => match keys.binary_search(x) { Ok(i) => i + 1, Err(i) => i, }, Bound::Excluded(x) => match keys.binary_search(x) { Ok(i) | Err(i) => i, }, }; (start, end) } } // }}}