結果
| 問題 | No.2676 A Tourist |
| ユーザー |
 ngtkana
|
| 提出日時 | 2024-03-02 01:16:01 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 946 ms / 5,000 ms |
| コード長 | 30,377 bytes |
| コンパイル時間 | 13,252 ms |
| コンパイル使用メモリ | 393,968 KB |
| 実行使用メモリ | 83,104 KB |
| 最終ジャッジ日時 | 2024-09-29 23:14:30 |
| 合計ジャッジ時間 | 28,811 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 |
ソースコード
use hld::Hld;use input::input_array;use input::input_vec;use segtree::Segtree;fn main() {let [n, q] = input_array::<usize, 2>();let init = input_vec::<i64>();let mut g = vec![Vec::new(); n];for _ in 0..n - 1 {let [i, j] = input_array::<usize, 2>();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::<O>::new(vec![0; n]);let mut b = Segtree::<O>::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::<i64, 3>();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<Vec<usize>>,size: Vec<usize>,time: Vec<usize>,ord: Vec<usize>,parent: Vec<usize>,head: Vec<usize>,}impl Hld {pub fn new(root: usize, g: &[Vec<usize>]) -> Self {let (child, [size, time, ord, parent, head]) = hld(root, g);Self {child,size,time,ord,parent,head,}}pub fn child(&self) -> &[Vec<usize>] {&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::<usize>()}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<Self::Item> {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<Self::Item> {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<usize>]) -> (Vec<Vec<usize>>, [Vec<usize>; 5]) {let n = g.len();let mut size = vec![1; n];let mut child = vec![Vec::<usize>::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<usize>], size: &mut [usize], child: &mut [Vec<usize>]) {let mut gx = g[x].iter().copied().filter(|&y| y != p).collect::<Vec<_>>();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<usize>],time: &mut [usize],ord: &mut Vec<usize>,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<Lines<BufReader<Stdin>>>;static ONCE: Once = Once::new();pub struct Lazy(Cell<Option<Server>>);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<T, E> ForceFromStr for TwhereT: FromStr<Err = E>,E: std::fmt::Debug,{fn force_from_str(s: &str) -> Self {s.parse().unwrap()}}pub fn input_array<T: ForceFromStr, const N: usize>() -> [T; N]whereT: std::fmt::Debug,{<[_; N]>::try_from(input_vec()).unwrap()}pub fn input_vec<T: ForceFromStr>() -> Vec<T> {line().split_whitespace().map(T::force_from_str).collect::<Vec<_>>()}pub fn input<T: ForceFromStr>() -> 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<O: Ops> {table: Box<[O::Value]>,}impl<O: Ops> Segtree<O> {pub fn new<I: ExactSizeIterator<Item = O::Value>,T: IntoIterator<Item = O::Value, IntoIter = I>,>(iter: T,) -> Self {let iter = iter.into_iter();let n = iter.len();let mut table = repeat_with(O::Value::default).take(n).collect::<Vec<_>>();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<usize>) -> 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<usize>,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<usize>,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<O: Ops, Idx: SliceIndex<[O::Value], Output = O::Value>> Index<Idx> for Segtree<O> {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<O>,}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<O: Ops> Deref for Entry<'_, O> {type Target = O::Value;fn deref(&self) -> &Self::Target {&self.seg.as_slice()[self.idx]}}impl<O: Ops> DerefMut for Entry<'_, O> {fn deref_mut(&mut self) -> &mut Self::Target {&mut self.seg.as_slice_mut()[self.idx]}}impl<O: Ops> From<Vec<O::Value>> for Segtree<O> {fn from(v: Vec<O::Value>) -> Self {Self::new(v)}}impl<O: Ops> FromIterator<O::Value> for Segtree<O> {fn from_iter<T: IntoIterator<Item = O::Value>>(iter: T) -> Self {let mut v = iter.into_iter().collect::<VecDeque<_>>();let n = v.len();let mut table = repeat_with(O::Value::default).take(n).collect::<VecDeque<_>>();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<O: Ops> AsRef<[O::Value]> for Segtree<O> {fn as_ref(&self) -> &[O::Value] {&self.table[self.len()..]}}impl<O: Ops> AsMut<[O::Value]> for Segtree<O> {fn as_mut(&mut self) -> &mut [O::Value] {let n = self.len();&mut self.table[n..]}}impl<O: Ops> Debug for Segtree<O> {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<usize>) -> Range<usize> {#[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<str>) -> 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<usize>,table_name: String,rows: Vec<Row>,}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<String>) -> &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<Item = usize>) -> &mut Self {self.verticalbars.extend(verticalbar);self}pub fn table_name(&mut self, table_name: impl Into<String>) -> &mut Self {self.table_name = table_name.into();self}pub fn row(&mut self,label: impl Into<String>,values: impl IntoIterator<Item = impl fmt::Debug>,) -> &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<String>,}#[doc(hidden)]pub struct StringTable {head: StringRow,body: Vec<StringRow>,verticalbar_count: Vec<usize>,}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::<Vec<_>>();// Headinggray(f)?;write!(f,"{}",head.to_string(label_width, &value_width, verticalbar_count, true))?;resetln(f)?;// Bodyfor row in body {write!(f,"{}",row.to_string(label_width, &value_width, verticalbar_count, false))?;writeln!(f)?;}Ok(())}}struct StringRow {label: String,values: Vec<String>,}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:<label_width$} |")} else {format!("{label:^label_width$} |")});for j in 0..w {let value_width = value_width[j];s.push_str("|".repeat(varticalbars_count[j]).as_str());if varticalbars_count[j] == 0 && j != 0 && value_width <= 1 {s.push(' ');}match values.get(j) {Some(value) => {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<B, I>(iter: I) -> StringwhereB: Borrow<bool>,I: IntoIterator<Item = B>,{format!("[{}]",iter.into_iter().map(|b| ['.', '#'][usize::from(*(b.borrow()))]).collect::<String>(),)}}// }}}