use hld::Hld; use input::input_array; use input::input_vec; use segtree::Segtree; fn main() { let [n, q] = input_array::(); let init = input_vec::(); let mut g = vec![Vec::new(); n]; for _ in 0..n - 1 { let [i, j] = input_array::(); let i = i - 1; let j = j - 1; g[i].push(j); g[j].push(i); } let hld = Hld::new(0, &g); let mut a = Segtree::::new(vec![0; n]); let mut b = Segtree::::new(vec![0; n]); for (i, &x) in init.iter().enumerate() { *a.entry(hld.time()[i]) += x; *b.entry(hld.time()[i]) += x; let p = hld.parent()[i]; if i != p { *b.entry(hld.time()[p]) += x; } } for _ in 0..q { let query = input_array::(); match query[0] { 0 => { let i = query[1] as usize - 1; let x = query[2]; *a.entry(hld.time()[i]) += x; *b.entry(hld.time()[i]) += x; let p = hld.parent()[i]; if i != p { *b.entry(hld.time()[p]) += x; } } 1 => { let i = query[1] as usize - 1; let j = query[2] as usize - 1; let mut ans = 0; for (start, end) in hld.iter_v(i, j) { assert!(start <= end); ans += b.fold(start..=end); } for (start, end) in hld.iter_e(i, j) { assert!(start <= end); ans -= a.fold(start..=end); } let lca = hld.lca(i, j); let p = hld.parent()[lca]; if lca != p { ans += a[hld.time()[p]]; } println!("{ans}"); } _ => unreachable!(), } } } enum O {} impl segtree::Ops for O { type Value = i64; fn op(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value { lhs + rhs } fn identity() -> Self::Value { 0 } } // hld {{{ #[allow(dead_code)] mod hld { use std::mem::swap; use std::usize::MAX; #[derive(Clone, Debug, Default, Hash, PartialEq, Eq)] pub struct Hld { child: Vec>, size: Vec, time: Vec, ord: Vec, parent: Vec, head: Vec, } impl Hld { pub fn new(root: usize, g: &[Vec]) -> Self { let (child, [size, time, ord, parent, head]) = hld(root, g); Self { child, size, time, ord, parent, head, } } pub fn child(&self) -> &[Vec] { &self.child } pub fn size(&self) -> &[usize] { &self.size } pub fn time(&self) -> &[usize] { &self.time } pub fn ord(&self) -> &[usize] { &self.ord } pub fn parent(&self) -> &[usize] { &self.parent } pub fn head(&self) -> &[usize] { &self.head } pub fn is_adjacent(&self, u: usize, v: usize) -> bool { self.parent[u] == v || u == self.parent[v] } pub fn adjacent_toward(&self, x: usize, toward: usize) -> usize { if self.is_ancestor_of(x, toward) { self.child[x] .iter() .copied() .find(|&y| self.is_ancestor_of(y, toward)) .unwrap() } else { self.parent[x] } } pub fn dist(&self, u: usize, v: usize) -> usize { self.iter_e(u, v).map(|(l, r)| r - l + 1).sum::() } pub fn lca(&self, u: usize, v: usize) -> usize { let (u, v) = self.iter_v(u, v).last().unwrap(); self.ord[u.min(v)] } pub fn is_ancestor_of(&self, p: usize, u: usize) -> bool { self.lca(p, u) == p } pub fn between(&self, a: usize, b: usize, c: usize) -> bool { let mid = self.time[b]; self.iter_v(a, c) .any(|(left, right)| (left..=right).contains(&mid)) } pub fn iter_v(&self, u: usize, v: usize) -> IterV<'_> { IterV { hld: self, u, v, finish: false, } } pub fn iter_e(&self, u: usize, v: usize) -> IterE<'_> { IterE { hld: self, u, v, finish: false, } } } #[derive(Clone, Debug, Hash, PartialEq, Eq)] pub struct IterV<'a> { hld: &'a Hld, u: usize, v: usize, finish: bool, } impl Iterator for IterV<'_> { type Item = (usize, usize); fn next(&mut self) -> Option { if self.finish { return None; } let Self { hld, u, v, .. } = self; if hld.time[*u] > hld.time[*v] { swap(u, v); } Some(if hld.head[*u] == hld.head[*v] { self.finish = true; (hld.time[*u], hld.time[*v]) } else { let h = hld.head[*v]; let ans = (hld.time[h], hld.time[*v]); *v = hld.parent[h]; ans }) } } #[derive(Clone, Debug, Hash, PartialEq, Eq)] pub struct IterE<'a> { hld: &'a Hld, u: usize, v: usize, finish: bool, } impl Iterator for IterE<'_> { type Item = (usize, usize); fn next(&mut self) -> Option { if self.finish { return None; } let Self { hld, u, v, .. } = self; if hld.time[*u] > hld.time[*v] { swap(u, v); } if hld.head[*u] == hld.head[*v] { self.finish = true; if *u == *v { None } else { Some((hld.time[*u] + 1, hld.time[*v])) } } else { let h = hld.head[*v]; let ans = (hld.time[h], hld.time[*v]); *v = hld.parent[h]; Some(ans) } } } fn hld(root: usize, g: &[Vec]) -> (Vec>, [Vec; 5]) { let n = g.len(); let mut size = vec![1; n]; let mut child = vec![Vec::::new(); n]; dfs(root, root, g, &mut size, &mut child); let mut ord = Vec::new(); let mut time = vec![MAX; n]; let mut parent = vec![MAX; n]; let mut head = vec![MAX; n]; parent[root] = root; head[root] = root; efs(root, &child, &mut time, &mut ord, &mut parent, &mut head); (child, [size, time, ord, parent, head]) } fn dfs(x: usize, p: usize, g: &[Vec], size: &mut [usize], child: &mut [Vec]) { let mut gx = g[x].iter().copied().filter(|&y| y != p).collect::>(); if !gx.is_empty() { for &y in &gx { dfs(y, x, g, size, child); size[x] += size[y]; } let max_position = (0..gx.len()).max_by_key(|&i| size[gx[i]]).unwrap(); gx.swap(0, max_position); } child[x] = gx; } fn efs( x: usize, g: &[Vec], time: &mut [usize], ord: &mut Vec, parent: &mut [usize], head: &mut [usize], ) { time[x] = ord.len(); ord.push(x); if !g[x].is_empty() { let h = g[x][0]; head[h] = head[x]; parent[h] = x; efs(h, g, time, ord, parent, head); for &y in &g[x][1..] { head[y] = y; parent[y] = x; efs(y, g, time, ord, parent, head); } } } } // }}} // input {{{ #[allow(dead_code)] mod input { use std::cell::Cell; use std::convert::TryFrom; use std::io::stdin; use std::io::BufRead; use std::io::BufReader; use std::io::Lines; use std::io::Stdin; use std::str::FromStr; use std::sync::Mutex; use std::sync::Once; type Server = Mutex>>; static ONCE: Once = Once::new(); pub struct Lazy(Cell>); unsafe impl Sync for Lazy {} fn line() -> String { static SYNCER: Lazy = Lazy(Cell::new(None)); ONCE.call_once(|| { SYNCER .0 .set(Some(Mutex::new(BufReader::new(stdin()).lines()))); }); unsafe { (*SYNCER.0.as_ptr()) .as_ref() .unwrap() .lock() .unwrap() .next() .unwrap() .unwrap() } } pub trait ForceFromStr: FromStr { fn force_from_str(s: &str) -> Self; } impl ForceFromStr for T where T: FromStr, E: std::fmt::Debug, { fn force_from_str(s: &str) -> Self { s.parse().unwrap() } } pub fn input_array() -> [T; N] where T: std::fmt::Debug, { <[_; N]>::try_from(input_vec()).unwrap() } pub fn input_vec() -> Vec { line() .split_whitespace() .map(T::force_from_str) .collect::>() } pub fn input() -> T { T::force_from_str(&line()) } } // }}} // segtree {{{ #[allow(dead_code)] mod segtree { use std::collections::VecDeque; use std::fmt::Debug; use std::iter::repeat_with; use std::iter::FromIterator; use std::ops::Bound; use std::ops::Deref; use std::ops::DerefMut; use std::ops::Index; use std::ops::Range; use std::ops::RangeBounds; use std::slice::SliceIndex; pub trait Ops { type Value: Debug + Default; fn op(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value; fn identity() -> Self::Value; } pub struct Segtree { table: Box<[O::Value]>, } impl Segtree { pub fn new< I: ExactSizeIterator, T: IntoIterator, >( iter: T, ) -> Self { let iter = iter.into_iter(); let n = iter.len(); let mut table = repeat_with(O::Value::default).take(n).collect::>(); table.extend(iter); (1..n) .rev() .for_each(|i| table[i] = O::op(&table[2 * i], &table[2 * i + 1])); let table = table.into_boxed_slice(); Self { table } } pub fn is_empty(&self) -> bool { self.table.is_empty() } pub fn len(&self) -> usize { self.table.len() / 2 } pub fn fold(&self, range: impl RangeBounds) -> O::Value { let mut left = O::identity(); let mut right = O::identity(); let Range { mut start, mut end } = into_slice_range(self.len(), range); if end < start { segtree_index_order_fail(start, end); } if self.len() < end { segtree_end_index_len_fail(end, self.len()); } start += self.len(); end += self.len(); while start != end { if start % 2 == 1 { left = O::op(&left, &self.table[start]); start += 1; } if end % 2 == 1 { end -= 1; right = O::op(&self.table[end], &right); } start /= 2; end /= 2; } O::op(&left, &right) } pub fn max_right( &self, range: impl RangeBounds, mut pred: impl FnMut(&O::Value) -> bool, ) -> usize { let Range { mut start, mut end } = into_slice_range(self.len(), range); if start == end { start } else { start += self.len(); end += self.len(); let orig_end = end; let mut crr = O::identity(); let mut shift = 0; while start != end { if start % 2 == 1 { let nxt = O::op(&crr, &self.table[start]); if !pred(&nxt) { return self.max_right_subtree(crr, start, pred); } crr = nxt; start += 1; } start /= 2; end /= 2; shift += 1; } for p in (0..shift).rev() { let end = (orig_end >> p) - 1; if end % 2 == 0 { let nxt = O::op(&crr, &self.table[end]); if !pred(&nxt) { return self.max_right_subtree(crr, end, pred); } crr = nxt; } } orig_end - self.len() } } fn max_right_subtree( &self, mut crr: O::Value, mut root: usize, mut pred: impl FnMut(&O::Value) -> bool, ) -> usize { while root < self.len() { let nxt = O::op(&crr, &self.table[root * 2]); root = if pred(&nxt) { crr = nxt; root * 2 + 1 } else { root * 2 }; } root - self.len() } pub fn max_left( &self, range: impl RangeBounds, mut pred: impl FnMut(&O::Value) -> bool, ) -> usize { let Range { mut start, mut end } = into_slice_range(self.len(), range); if start == end { start } else { start += self.len(); end += self.len(); let orig_start_m1 = start - 1; let mut crr = O::identity(); let mut shift = 0; while start != end { if end % 2 == 1 { end -= 1; let nxt = O::op(&self.table[end], &crr); if !pred(&nxt) { return self.max_left_subtree(crr, end, pred); } crr = nxt; } start = (start + 1) >> 1; end >>= 1; shift += 1; } for p in (0..shift).rev() { let start = (orig_start_m1 >> p) + 1; if start % 2 == 1 { let nxt = O::op(&self.table[start], &crr); if !pred(&nxt) { return self.max_left_subtree(crr, start, pred); } crr = nxt; } } orig_start_m1 + 1 - self.len() } } fn max_left_subtree( &self, mut crr: O::Value, mut root: usize, mut pred: impl FnMut(&O::Value) -> bool, ) -> usize { while root < self.len() { let nxt = O::op(&self.table[root * 2 + 1], &crr); root = if pred(&nxt) { crr = nxt; root * 2 } else { root * 2 + 1 }; } root + 1 - self.len() } pub fn entry(&mut self, idx: usize) -> Entry<'_, O> { Entry { idx, seg: self } } pub fn as_slice(&self) -> &[O::Value] { self.as_ref() } pub fn as_slice_mut(&mut self) -> &mut [O::Value] { self.as_mut() } } // 隕∫エ繧「繧ッ繧サ繧ケ impl> Index for Segtree { type Output = O::Value; fn index(&self, index: Idx) -> &Self::Output { &self.as_slice()[index] } } pub struct Entry<'a, O: Ops> { idx: usize, seg: &'a mut Segtree, } impl<'a, O: Ops> Drop for Entry<'a, O> { fn drop(&mut self) { self.idx += self.seg.len(); self.idx /= 2; while self.idx != 0 { self.seg.table[self.idx] = O::op( &self.seg.table[2 * self.idx], &self.seg.table[2 * self.idx + 1], ); self.idx /= 2; } } } impl Deref for Entry<'_, O> { type Target = O::Value; fn deref(&self) -> &Self::Target { &self.seg.as_slice()[self.idx] } } impl DerefMut for Entry<'_, O> { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.seg.as_slice_mut()[self.idx] } } impl From> for Segtree { fn from(v: Vec) -> Self { Self::new(v) } } impl FromIterator for Segtree { fn from_iter>(iter: T) -> Self { let mut v = iter.into_iter().collect::>(); let n = v.len(); let mut table = repeat_with(O::Value::default) .take(n) .collect::>(); table.append(&mut v); (1..n) .rev() .for_each(|i| table[i] = O::op(&table[2 * i], &table[2 * i + 1])); let table = Vec::from(table).into_boxed_slice(); Self { table } } } impl AsRef<[O::Value]> for Segtree { fn as_ref(&self) -> &[O::Value] { &self.table[self.len()..] } } impl AsMut<[O::Value]> for Segtree { fn as_mut(&mut self) -> &mut [O::Value] { let n = self.len(); &mut self.table[n..] } } impl Debug for Segtree { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { self.as_slice().fmt(f) } } fn into_slice_range(len: usize, range: impl RangeBounds) -> Range { #[allow(clippy::redundant_closure)] let start = match range.start_bound() { Bound::Included(&start) => start, Bound::Excluded(&start) => start .checked_add(1) .unwrap_or_else(|| slice_start_index_overflow_fail()), Bound::Unbounded => 0, }; #[allow(clippy::redundant_closure)] let end = match range.end_bound() { Bound::Included(&end) => end .checked_add(1) .unwrap_or_else(|| slice_end_index_overflow_fail()), Bound::Excluded(&end) => end, Bound::Unbounded => len, }; start..end } fn segtree_end_index_len_fail(index: usize, len: usize) -> ! { panic!( "range end index {} out of range for segtree of length {}", index, len ); } fn segtree_index_order_fail(index: usize, end: usize) -> ! { panic!("segtree index starts at {} but ends at {}", index, end); } fn slice_start_index_overflow_fail() -> ! { panic!("attempted to index slice from after maximum usize"); } fn slice_end_index_overflow_fail() -> ! { panic!("attempted to index slice up to maximum usize"); } } // }}} // lg {{{ #[allow(dead_code)] mod lg { use std::borrow::Borrow; use std::fmt; use std::iter::once; #[macro_export] macro_rules! lg { (@contents $head:expr $(, $tail:expr)*) => {{ $crate::__lg_internal!($head); $( eprint!(","); $crate::__lg_internal!($tail); )* eprintln!(); }}; ($($expr:expr),* $(,)?) => {{ eprint!("{}笶ッ", line!()); $crate::lg!(@contents $($expr),*) }}; } #[doc(hidden)] #[macro_export] macro_rules! __lg_internal { ($value:expr) => {{ match $value { head => { eprint!( " {} = {}", stringify!($value), $crate::lg::__quiet(format!("{:?}", &head)) ); } } }}; } #[macro_export] macro_rules! rows { { $index_label:literal, $(@offset $offset:expr,)? $(@verticalbar $verticalbar:expr,)* $($(@$label:literal =>)? $values:expr),* $(,)? } => {{ #![allow(unused_assignments)] let mut rows = $crate::lg::Rows::default(); rows.line_number(line!()); $(rows.offset($offset);)? $(rows.verticalbar($verticalbar);)* rows.index_label($index_label); $({ let mut label = stringify!($values).to_string(); if label.starts_with("&") { label = label[1..].to_string(); } $({ let label_: &'static str = $label; label = label_.to_string(); })? rows.row(label, $values); })* eprintln!("{}", rows.to_string_table()); }}; } #[macro_export] macro_rules! table { { $(@$name:literal => )? $values:expr $(,)? } => {{ #![allow(unused_assignments)] let mut name = stringify!($values).to_string(); if name.starts_with("&") { name = name[1..].to_string(); } $({ let name_: &'static str = $name; name = name_.to_string(); })? let mut rows = $crate::lg::Rows::default(); rows.line_number(line!()); rows.table_name(name); #[allow(array_into_iter)] for (i, row) in $values.into_iter().enumerate() { rows.row(i.to_string(), row); } eprintln!("{}", rows.to_string_table()); }}; } #[doc(hidden)] pub fn __quiet(s: impl AsRef) -> String { s.as_ref() .replace("340282366920938463463374607431768211455", "*") // u128 .replace("170141183460469231731687303715884105727", "*") // i128 .replace("18446744073709551615", "*") // u64 .replace("9223372036854775807", "*") // i64 .replace("-9223372036854775808", "*") // i64 .replace("4294967295", "*") // u32 .replace("2147483647", "*") // i32 .replace("-2147483648", "*") // i32 .replace("None", "*") .replace("Some", "") .replace("true", "#") .replace("false", ".") .replace(['"', '\''], "") } #[doc(hidden)] #[derive(Default)] pub struct Rows { line_number: String, index_label: String, offset: usize, verticalbars: Vec, table_name: String, rows: Vec, } impl Rows { pub fn line_number(&mut self, line_number: u32) -> &mut Self { self.line_number = format!("{}", line_number); self } pub fn index_label(&mut self, index_label: impl Into) -> &mut Self { self.index_label = index_label.into(); self } pub fn offset(&mut self, offset: usize) -> &mut Self { self.offset = offset; self } pub fn verticalbar(&mut self, verticalbar: impl IntoIterator) -> &mut Self { self.verticalbars.extend(verticalbar); self } pub fn table_name(&mut self, table_name: impl Into) -> &mut Self { self.table_name = table_name.into(); self } pub fn row( &mut self, label: impl Into, values: impl IntoIterator, ) -> &mut Self { self.rows.push(Row { label: label.into(), values: values .into_iter() .map(|value| __quiet(format!("{:?}", value))) .collect(), }); self } pub fn to_string_table(self) -> StringTable { let Self { line_number, index_label, offset, verticalbars, table_name, rows, } = self; let w = rows .iter() .map(|row| row.values.len()) .max() .unwrap_or_default(); let mut verticalbar_count = vec![0; w + 1]; for &v in &verticalbars { if (offset..=offset + w).contains(&v) { verticalbar_count[v - offset] += 1; } } StringTable { head: StringRow { label: format!( "{line_number}笶ッ {table_name}{index_label}", index_label = if index_label.is_empty() { String::new() } else { format!("[{}]", index_label) } ), values: (offset..offset + w) .map(|index| index.to_string()) .collect(), }, body: rows .iter() .map(|row| StringRow { label: row.label.clone(), values: row.values.clone(), }) .collect(), verticalbar_count, } } } struct Row { label: String, values: Vec, } #[doc(hidden)] pub struct StringTable { head: StringRow, body: Vec, verticalbar_count: Vec, } impl fmt::Display for StringTable { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let Self { head, body, verticalbar_count, } = self; let w = body .iter() .map(|row| row.values.len()) .max() .unwrap_or_default(); let label_width = once(head.label.chars().count()) .chain(body.iter().map(|row| row.label.chars().count())) .max() .unwrap(); let value_width = (0..w) .map(|j| { once(j.to_string().len()) .chain( body.iter() .map(|row| row.values.get(j).map_or(0, |s| s.chars().count())), ) .max() .unwrap() }) .collect::>(); // Heading gray(f)?; write!( f, "{}", head.to_string(label_width, &value_width, verticalbar_count, true) )?; resetln(f)?; // Body for row in body { write!( f, "{}", row.to_string(label_width, &value_width, verticalbar_count, false) )?; writeln!(f)?; } Ok(()) } } struct StringRow { label: String, values: Vec, } impl StringRow { fn to_string( &self, label_width: usize, value_width: &[usize], varticalbars_count: &[usize], label_align_left: bool, ) -> String { let Self { label, values } = self; let w = value_width.len(); let mut s = String::new(); s.push_str(&if label_align_left { format!("{label: { s.push_str(&format!(" {value:>value_width$}",)); } None => { s.push_str(" ".repeat(value_width + 1).as_str()); } } } s } } const GRAY: &str = "\x1b[48;2;127;127;127;37m"; const RESET: &str = "\x1b[0m"; fn gray(f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{GRAY}") } fn resetln(f: &mut fmt::Formatter<'_>) -> fmt::Result { writeln!(f, "{RESET}") } pub fn bools(iter: I) -> String where B: Borrow, I: IntoIterator, { format!( "[{}]", iter.into_iter() .map(|b| ['.', '#'][usize::from(*(b.borrow()))]) .collect::(), ) } } // }}}