Submit Info #16138

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum rust tmaehara AC 911 ms 29.65 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
max_random_00 AC 911 ms 29.52 MiB
max_random_01 AC 818 ms 29.52 MiB
max_random_02 AC 831 ms 29.65 MiB
random_00 AC 529 ms 19.46 MiB
random_01 AC 585 ms 22.31 MiB
random_02 AC 313 ms 9.67 MiB
random_03 AC 341 ms 21.42 MiB
random_04 AC 197 ms 4.41 MiB
small_00 AC 2 ms 0.71 MiB
small_01 AC 1 ms 0.68 MiB
small_02 AC 2 ms 0.70 MiB

pub trait Monoid { fn op(&self, other: &Self) -> Self; fn id() -> Self; } pub trait Action<M> { fn act(&self, other: &M) -> M; } impl Monoid for () { fn op(&self, _other: &Self) -> () { () } fn id() -> Self { () } } impl<T: Clone> Action<T> for () { fn act(&self, other: &T) -> T{ other.clone() } } #[derive(Debug)] struct Node<M,A> { value: M, fold: (M, M), // (path from root, path to root) action: A, rev: bool, child: [Option<usize>; 2], parent: Option<usize>, } impl<M,A> Node<M,A> where M: Monoid, A: Monoid + Action<M> { fn new() -> Self { Self { value: M::id(), fold: (M::id(), M::id()), action: A::id(), rev: false, child: [None,None], parent: None } } } #[derive(Debug)] pub struct LinkCutTree<M=(), A=()> { node: Vec<Node<M,A>>, } impl<M,A> LinkCutTree<M,A> where M: Clone + Monoid, A: Monoid + Action<M> { fn propagate(&mut self, u: usize) { if let Some(l) = self.node[u].child[0] { self.node[l].rev ^= self.node[u].rev; self.node[l].action = self.node[u].action.op(&self.node[l].action); } if let Some(r) = self.node[u].child[1] { self.node[r].rev ^= self.node[u].rev; self.node[r].action = self.node[u].action.op(&self.node[r].action); } if self.node[u].rev { self.node[u].rev = false; self.node[u].child.reverse(); let fold = &mut self.node[u].fold; std::mem::swap(&mut fold.0, &mut fold.1); } self.node[u].value = self.node[u].action.act(&self.node[u].value); self.node[u].fold.0 = self.node[u].action.act(&self.node[u].fold.0); self.node[u].fold.1 = self.node[u].action.act(&self.node[u].fold.1); self.node[u].action = A::id(); } fn update(&mut self, u: usize) { self.node[u].fold.0 = self.node[u].value.clone(); self.node[u].fold.1 = self.node[u].value.clone(); if let Some(l) = self.node[u].child[0] { self.node[u].fold.0 = self.node[l].fold.0.op(&self.node[u].fold.0); self.node[u].fold.1 = self.node[u].fold.1.op(&self.node[l].fold.1); } if let Some(r) = self.node[u].child[1] { self.node[u].fold.0 = self.node[u].fold.0.op(&self.node[r].fold.0); self.node[u].fold.1 = self.node[r].fold.1.op(&self.node[u].fold.1); } } fn direction(&self, u: usize) -> Option<usize> { if let Some(p) = self.node[u].parent { if self.node[p].child[0] == Some(u) { return Some(0); } if self.node[p].child[1] == Some(u) { return Some(1); } } return None; } fn rotate(&mut self, u: usize) { let p = self.node[u].parent.unwrap(); let d = self.direction(u).unwrap(); self.node[p].child[d] = self.node[u].child[1-d]; if let Some(c) = self.node[p].child[d] { self.node[c].parent = Some(p); } if let Some(d) = self.direction(p) { let g = self.node[p].parent.unwrap(); self.node[g].child[d] = Some(u); } self.node[u].parent = self.node[p].parent; self.node[u].child[1-d] = Some(p); self.node[p].parent = Some(u); self.update(p); self.update(u); if let Some(g) = self.node[u].parent { self.update(g); } } fn splay(&mut self, u: usize) { while self.direction(u).is_some() { let p = self.node[u].parent.unwrap(); if self.direction(p).is_some() { if self.direction(u) == self.direction(p) { self.rotate(p); } else { self.rotate(u); } } self.rotate(u); } } fn propagate_from_root(&mut self, u: usize) { if let Some(p) = self.node[u].parent { self.propagate_from_root(p); } self.propagate(u); } fn expose(&mut self, u: usize) -> usize { self.propagate_from_root(u); let mut r = None; let mut head = Some(u); while let Some(p) = head { self.splay(p); self.node[p].child[1] = r; self.update(p); r = Some(p); head = self.node[p].parent; } self.splay(u); r.unwrap() } pub fn new(n: usize) -> Self { Self { node: (0..n).map(|_| Node::new()).collect() } } pub fn link(&mut self, u: usize, p: usize) { self.expose(u); self.expose(p); assert!(self.node[p].child[1].is_none()); assert!(self.node[p].rev == false); assert!(self.node[u].rev == false); self.node[p].child[1] = Some(u); self.node[u].parent = Some(p); self.update(p); } pub fn cut(&mut self, u: usize) -> Option<usize> { self.expose(u); if let Some(y) = self.node[u].child[0].take() { self.node[y].parent = None; self.update(u); Some(y) } else { None } } pub fn lca(&mut self, u: usize, v: usize) -> Option<usize> { self.expose(u); let x = self.expose(v); self.node[u].parent.map(|_| x) } pub fn evert(&mut self, u: usize) { self.expose(u); self.node[u].rev ^= true; self.propagate(u); } pub fn get(&mut self, u: usize) -> &M { self.expose(u); &self.node[u].value } pub fn replace(&mut self, u: usize, value: M) -> M { self.expose(u); let last = std::mem::replace(&mut self.node[u].value, value); self.update(u); last } /// aggregate values from root to node pub fn fold(&mut self, u: usize) -> &M { self.expose(u); &self.node[u].fold.0 } /// aggregate values from node to root pub fn fold_to_root(&mut self, u: usize) -> &M { self.expose(u); &self.node[u].fold.1 } pub fn map(&mut self, u: usize, a: A) { self.expose(u); self.node[u].action = a.op(&self.node[u].action); } } // https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum #[derive(Clone,Debug)] struct M(i64,i64); impl Monoid for M { fn id() -> M { M(0,0) } fn op(&self, other: &Self) -> M { M(self.0+other.0, self.1+other.1) } } struct A(i64); impl Monoid for A { fn id() -> A { A(0) } fn op(&self, other: &Self) -> A { A(self.0+other.0) } } impl Action<M> for A { fn act(&self, other: &M) -> M { M(other.0 + other.1 * self.0, other.1) } } // check: // (x1,s1)^a + (x2,s2)^a = (x1 + a s1, s1) + (x2 + a s2, s2) // = (x1 + x2 + a (s1 + s2), s1 + s2) // ((x1,s1) + (x2,s2))^a = (x1 + x2, s1 + s2)^a // = (x1 + x2 + a (s1 + s2), s1 + s2) // // use std::io::Read; use std::io::Write; fn main() { let mut buf = String::new(); std::io::stdin().read_to_string(&mut buf).unwrap(); let mut reader = buf.trim().split_whitespace(); let n: usize = reader.next().unwrap().parse().unwrap(); let q: usize = reader.next().unwrap().parse().unwrap(); let mut tree: LinkCutTree<M,()> = LinkCutTree::new(n); for i in 0..n { let a: i64 = reader.next().unwrap().parse().unwrap(); tree.replace(i, M(a, 1)); } for i in 0..n-1 { let u: usize = reader.next().unwrap().parse().unwrap(); let v: usize = reader.next().unwrap().parse().unwrap(); tree.evert(u); tree.link(u,v); } for _ in 0..q { let t: usize = reader.next().unwrap().parse().unwrap(); match t { 0 => { let u: usize = reader.next().unwrap().parse().unwrap(); let v: usize = reader.next().unwrap().parse().unwrap(); let w: usize = reader.next().unwrap().parse().unwrap(); let x: usize = reader.next().unwrap().parse().unwrap(); // remove(u,v) // add(w,x) tree.evert(u); let check = tree.cut(v); assert_eq!(check, Some(u)); tree.evert(x); tree.link(x,w); } 1 => { let p: usize = reader.next().unwrap().parse().unwrap(); let x: i64 = reader.next().unwrap().parse().unwrap(); let a = tree.get(p).clone(); tree.replace(p, M(a.0+x, a.1)); }, 2 => { let u: usize = reader.next().unwrap().parse().unwrap(); let v: usize = reader.next().unwrap().parse().unwrap(); tree.evert(u); println!("{}", tree.fold(v).0); }, _ => unreachable!(), } } }