Submit Info #3371

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

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
max_random_00 AC 790 ms 29.40 MiB
max_random_01 AC 756 ms 29.40 MiB
max_random_02 AC 791 ms 29.52 MiB
random_00 AC 481 ms 19.41 MiB
random_01 AC 538 ms 22.16 MiB
random_02 AC 266 ms 9.67 MiB
random_03 AC 329 ms 21.36 MiB
random_04 AC 158 ms 4.41 MiB
small_00 AC 2 ms 0.71 MiB
small_01 AC 2 ms 0.67 MiB
small_02 AC 2 ms 0.68 MiB

use std::cell::*; use std::rc::*; type Link = Option<Rc<RefCell<Node>>>; type WeakLink = Option<Weak<RefCell<Node>>>; #[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(t: &Link) -> usize { t.as_ref().map_or(0, |t| t.borrow().size) } fn get_sum(t: &Link) -> u64 { t.as_ref().map_or(0, |t| t.borrow().sum) } fn assign_label(t: &Link, label: Label) { if let Some(t) = t.as_ref() { t.borrow_mut().label = label; } } fn push(t: &Link) { let mut t_mut = t .as_ref() .unwrap() .try_borrow_mut() .expect("push error: borrow"); if t_mut.rev { if let Some(p) = t_mut.left.as_ref() { assert!(p.borrow().label == Label::Left); p.borrow_mut().rev ^= true; p.borrow_mut().label = Label::Right; } if let Some(p) = t_mut.right.as_ref() { assert!(p.borrow().label == Label::Right); 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(t: &Link) { if t.is_none() { return; } let t = t.as_ref().unwrap(); let mut po = t.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: &Link) { assert!(t.as_ref().unwrap().borrow().label == Label::Right); assert!(!t.as_ref().unwrap().borrow().rev); assert!(t.as_ref().unwrap().borrow().parent.is_some()); let mut t_mut = t.as_ref().unwrap().borrow_mut(); let l = t_mut.left.take(); t_mut.left = t_mut.parent.clone().unwrap().upgrade(); if let Some(l) = l.as_ref() { let mut l_mut = l.borrow_mut(); assert!(l_mut.label == Label::Left); l_mut.parent = t_mut.parent.clone(); l_mut.label = Label::Right; } let parent = t_mut.parent.take().unwrap().upgrade(); let mut parent_mut = parent.as_ref().unwrap().borrow_mut(); assert!(!parent_mut.rev); let label = parent_mut.label; parent_mut.right = l; parent_mut.label = Label::Left; let q = parent_mut.parent.take(); parent_mut.parent = Some(Rc::downgrade(t.as_ref().unwrap())); drop(parent_mut); t_mut.label = label; t_mut.parent = q.clone(); match label { Label::Root => {}, Label::Left => { q.as_ref().unwrap().upgrade().unwrap().borrow_mut().left = t.clone(); }, Label::Right => { q.as_ref().unwrap().upgrade().unwrap().borrow_mut().right = t.clone(); }, } update(&t_mut.left); drop(t_mut); update(&t); } fn right_rotate(t: &Link) { assert!(t.as_ref().unwrap().borrow().label == Label::Left); assert!(!t.as_ref().unwrap().borrow().rev); assert!(t.as_ref().unwrap().borrow().parent.is_some()); let mut t_mut = t.as_ref().unwrap().borrow_mut(); let r = t_mut.right.take(); t_mut.right = t_mut.parent.clone().unwrap().upgrade(); if let Some(r) = r.as_ref() { let mut r_mut = r.borrow_mut(); assert!(r_mut.label == Label::Right); r_mut.parent = t_mut.parent.clone(); r_mut.label = Label::Left; } let parent = t_mut.parent.take().unwrap().upgrade(); let mut parent_mut = parent.as_ref().unwrap().borrow_mut(); assert!(!parent_mut.rev); let label = parent_mut.label; parent_mut.left = r; parent_mut.label = Label::Right; let q = parent_mut.parent.take(); parent_mut.parent = Some(Rc::downgrade(t.as_ref().unwrap())); drop(parent_mut); t_mut.label = label; t_mut.parent = q.clone(); match label { Label::Root => {}, Label::Left => { q.as_ref().unwrap().upgrade().unwrap().borrow_mut().left = t.clone(); }, Label::Right => { q.as_ref().unwrap().upgrade().unwrap().borrow_mut().right = t.clone(); }, } update(&t_mut.right); drop(t_mut); update(&t); } fn splay(t: &Link) { assert!(t.is_some()); push(t); while t.as_ref().unwrap().borrow().label != Label::Root { let p = t.as_ref().expect("label err").borrow().parent.clone().expect("parent none but not root").upgrade(); if p.as_ref().unwrap().borrow().label == Label::Root { push(&p); push(&t); let label = t.as_ref().unwrap().borrow().label; match label { Label::Right => left_rotate(t), Label::Left => right_rotate(t), _ => unreachable!(), } } else { let q = p.as_ref().expect("label 2").borrow().parent.clone().unwrap().upgrade(); push(&q); push(&p); push(&t); let x = p.as_ref().unwrap().borrow().label; let y = t.as_ref().unwrap().borrow().label; 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: &Link) { let mut rp: Link = None; let mut cur = x.clone(); loop { splay(&cur); assert!(!cur.as_ref().unwrap().borrow().rev); assert!(rp.as_ref().map_or(Label::Root, |t| t.borrow().label) == Label::Root); assign_label(&cur.as_ref().unwrap().borrow().right, Label::Root); if let Some(rp) = rp.as_ref() { rp.borrow_mut().parent = Some(Rc::downgrade(&cur.clone().unwrap())); rp.borrow_mut().label = Label::Right; } cur.as_ref().unwrap().borrow_mut().right = rp; assert!(x.as_ref().unwrap().borrow_mut().right.is_none()); update(&cur); let next = cur.as_ref().unwrap().borrow().parent.clone(); if let Some(next) = next { let next = next.upgrade(); rp = cur; cur = next; } else { break; } } splay(x); assert!(x.as_ref().unwrap().borrow().parent.is_none()); assert!(x.as_ref().unwrap().borrow().right.is_none()); } fn cut(c: &Link) { expose(c); assert!(c.as_ref().unwrap().borrow().label == Label::Root); let mut c_mut = c.as_ref().unwrap().borrow_mut(); let lp = c_mut.left.take(); assert!(lp.is_some()); let mut lp = lp.as_ref().unwrap().borrow_mut(); assert!(lp.label == Label::Left); lp.parent = None; // c_mut.left = None; lp.label = Label::Root; drop(c_mut); update(c); } fn link(c: &Link, p: &Link) { expose(c); expose(p); assert!(c.as_ref().unwrap().borrow().parent.is_none()); assert!(c.as_ref().unwrap().borrow().label == Label::Root); assert!(p.as_ref().unwrap().borrow().parent.is_none()); assert!(p.as_ref().unwrap().borrow().label == Label::Root); assign_label(c, Label::Right); // assign_label(&p.as_ref().unwrap().borrow().right, Label::Root); c.as_ref().unwrap().borrow_mut().parent = Some(Rc::downgrade(&p.clone().unwrap())); p.as_ref().unwrap().borrow_mut().right = c.clone(); update(p); } fn evert(v: &Link) { expose(v); v.as_ref().unwrap().borrow_mut().rev ^= true; push(v); let po = v.as_ref().unwrap().borrow(); assert!(po.label == Label::Root); assert!(po.left.is_none()); assert!(po.parent.is_none()); } 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 = Some(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].as_ref().unwrap().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 = get_sum(&node[b]); writeln!(out, "{}", ans).ok(); } /* for i in 0..n { let po = node[i].as_ref().unwrap().borrow(); write!(out, "({}, {:?}) ", po.sum, po.label).ok(); } writeln!(out, "").ok(); */ } } fn main() { run(); }