Submit Info #3940

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum rust sansen AC 645 ms 29.53 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 645 ms 29.40 MiB
max_random_01 AC 622 ms 29.48 MiB
max_random_02 AC 633 ms 29.53 MiB
random_00 AC 403 ms 19.29 MiB
random_01 AC 446 ms 22.16 MiB
random_02 AC 227 ms 9.67 MiB
random_03 AC 277 ms 21.41 MiB
random_04 AC 138 ms 4.42 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 1 ms 0.68 MiB
small_02 AC 1 ms 0.73 MiB

use std::cell::*; use std::rc::*; type Ref = Rc<RefCell<Node>>; type WeakRef = Weak<RefCell<Node>>; type Link = Option<Ref>; type WeakLink = Option<WeakRef>; #[derive(PartialEq, Eq, Clone, Copy, Debug)] enum Label { Root, Left, Right, } struct Node { label: Label, rev: bool, val: u64, sum: u64, size: usize, parent: WeakLink, left: Link, right: Link, } fn get_size(node: &Link) -> usize { node.as_ref().map_or(0, |t| t.borrow().size) } fn get_sum(node: &Link) -> u64 { node.as_ref().map_or(0, |t| t.borrow().sum) } fn get_label(node: &Ref) -> Label { node.borrow().label } fn assign_label(node: &Link, label: Label) { if let Some(node) = node.as_ref() { node.borrow_mut().label = label; } } fn push(t: &Ref) { let mut t_mut = t.borrow_mut(); if t_mut.rev { if let Some(p) = t_mut.left.as_ref() { p.borrow_mut().rev ^= true; p.borrow_mut().label = Label::Right; } if let Some(p) = t_mut.right.as_ref() { p.borrow_mut().rev ^= true; p.borrow_mut().label = Label::Left; } let p = t_mut.left.take(); t_mut.left = t_mut.right.take(); t_mut.right = p; t_mut.rev = false; } } fn update(node: &Ref) { let mut po = node.borrow_mut(); po.size = 1 + get_size(&po.left) + get_size(&po.right); po.sum = po.val + get_sum(&po.left) + get_sum(&po.right); } fn left_rotate(t: &Ref) { let mut t_mut = t.borrow_mut(); let left = t_mut.left.take(); if let Some(left) = left.as_ref() { let mut left_mut = left.borrow_mut(); left_mut.parent = t_mut.parent.clone(); left_mut.label = Label::Right; } let parent = t_mut.parent.clone().unwrap().upgrade().unwrap(); let mut parent_mut = parent.borrow_mut(); let qarent = parent_mut.parent.take(); let label = parent_mut.label; parent_mut.right = left; parent_mut.parent = Some(Rc::downgrade(t)); parent_mut.label = Label::Left; drop(parent_mut); t_mut.left = Some(parent.clone()); t_mut.label = label; t_mut.parent = qarent.clone(); drop(t_mut); match label { Label::Root => {}, Label::Left => { qarent.as_ref().unwrap().upgrade().unwrap().borrow_mut().left = Some(t.clone()); }, Label::Right => { qarent.as_ref().unwrap().upgrade().unwrap().borrow_mut().right = Some(t.clone()); }, } update(&parent); update(t); } fn right_rotate(t: &Ref) { let mut t_mut = t.borrow_mut(); let right = t_mut.right.take(); if let Some(right) = right.as_ref() { let mut right_mut = right.borrow_mut(); right_mut.parent = t_mut.parent.clone(); right_mut.label = Label::Left; } let parent = t_mut.parent.clone().unwrap().upgrade().unwrap(); let mut parent_mut = parent.borrow_mut(); let qarent = parent_mut.parent.take(); let label = parent_mut.label; parent_mut.left = right; parent_mut.parent = Some(Rc::downgrade(t)); parent_mut.label = Label::Right; drop(parent_mut); t_mut.right = Some(parent.clone()); t_mut.label = label; t_mut.parent = qarent.clone(); drop(t_mut); match label { Label::Root => {}, Label::Left => { qarent.as_ref().unwrap().upgrade().unwrap().borrow_mut().left = Some(t.clone()); }, Label::Right => { qarent.as_ref().unwrap().upgrade().unwrap().borrow_mut().right = Some(t.clone()); }, } update(&parent); update(t); } fn splay(t: &Ref) { push(t); while get_label(t) != Label::Root { let p = t.borrow().parent.clone().unwrap().upgrade().unwrap(); if get_label(&p) == Label::Root { push(&p); push(t); let label = get_label(t); match label { Label::Left => right_rotate(t), Label::Right => left_rotate(t), _ => unreachable!(), } } else { let q = p.borrow().parent.clone().unwrap().upgrade().unwrap(); push(&q); push(&p); push(t); let x = get_label(&p); let y = get_label(t); match (x, y) { (Label::Left, Label::Left) => { right_rotate(&p); right_rotate(t); }, (Label::Left, Label::Right) => { left_rotate(t); right_rotate(t); }, (Label::Right, Label::Left) => { right_rotate(t); left_rotate(t); }, (Label::Right, Label::Right) => { left_rotate(&p); left_rotate(t); }, _ => unreachable!(), } } } } fn expose(x: &Ref) { let mut rp: Link = None; let mut cur = x.clone(); loop { splay(&cur); assign_label(&cur.borrow().right, Label::Root); if let Some(rp) = rp.as_ref() { let mut po = rp.borrow_mut(); po.parent = Some(Rc::downgrade(&cur.clone())); po.label = Label::Right; } cur.borrow_mut().right = rp; update(&cur); let next = cur.borrow().parent.clone(); if let Some(next) = next { let next = next.upgrade().unwrap(); rp = Some(cur); cur = next; } else { break; } } splay(x); } fn cut(c: &Ref) { expose(c); let lp = c.borrow_mut().left.take(); let mut lp_mut = lp.as_ref().expect("cut error").borrow_mut(); lp_mut.parent = None; lp_mut.label = Label::Root; update(c); } fn link(c: &Ref, p: &Ref) { expose(c); expose(p); assert!(c.borrow().parent.is_none()); let mut c_mut = c.borrow_mut(); c_mut.label = Label::Right; c_mut.parent = Some(Rc::downgrade(&p.clone())); drop(c_mut); p.borrow_mut().right = Some(c.clone()); update(p); } fn evert(v: &Ref) { expose(v); v.borrow_mut().rev ^= true; } use std::io::Read; use std::io::Write; fn run() { let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let n: usize = it.next().unwrap().parse().unwrap(); let q: usize = it.next().unwrap().parse().unwrap(); let mut node = vec![]; for _ in 0..n { let a: u64 = it.next().unwrap().parse().unwrap(); let t = Rc::new(RefCell::new(Node { label: Label::Root, rev: false, val: a, sum: a, size: 1, parent: None, left: None, right: None, })); node.push(t); } for _ in 1..n { let a: usize = it.next().unwrap().parse().unwrap(); let b: usize = it.next().unwrap().parse().unwrap(); evert(&node[a]); link(&node[a], &node[b]); } for _ in 0..q { let op: usize = it.next().unwrap().parse().unwrap(); if op == 0 { let a: usize = it.next().unwrap().parse().unwrap(); let b: usize = it.next().unwrap().parse().unwrap(); let c: usize = it.next().unwrap().parse().unwrap(); let d: usize = it.next().unwrap().parse().unwrap(); evert(&node[a]); cut(&node[b]); evert(&node[c]); link(&node[c], &node[d]); } else if op == 1 { let p: usize = it.next().unwrap().parse().unwrap(); let x: u64 = it.next().unwrap().parse().unwrap(); expose(&node[p]); node[p].borrow_mut().val += x; update(&node[p]); } else { let a: usize = it.next().unwrap().parse().unwrap(); let b: usize = it.next().unwrap().parse().unwrap(); evert(&node[a]); expose(&node[b]); let ans = node[b].borrow().sum; writeln!(out, "{}", ans).ok(); } } } fn main() { run(); }