#433595 (Rust) No.235 めぐるはめぐる (5)

• 問題: No.235 めぐるはめぐる (5)
• ユーザー: akakimidori
• 提出日時: 2020-02-22 22:38:31
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 1,431 ms / 10,000 ms
• コード長: 15,289 bytes
• コンパイル時間: 13,937 ms
• コンパイル使用メモリ: 382,548 KB
• 実行使用メモリ: 34,492 KB
• 最終ジャッジ日時: 2024-10-09 23:30:55
• 合計ジャッジ時間: 19,832 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
other	AC * 3

ソースコード

// ---------- begin ModInt ----------
const MOD: u32 = 1_000_000_007;

#[derive(Clone, Copy)]
struct ModInt(u32);

impl std::ops::Add for ModInt {
    type Output = ModInt;
    fn add(self, rhs: ModInt) -> Self::Output {
        let mut d = self.0 + rhs.0;
        if d >= MOD {
            d -= MOD;
        }
        ModInt(d)
    }
}

impl std::ops::AddAssign for ModInt {
    fn add_assign(&mut self, rhs: ModInt) {
        *self = *self + rhs;
    }
}

impl std::ops::Sub for ModInt {
    type Output = ModInt;
    fn sub(self, rhs: ModInt) -> Self::Output {
        let mut d = self.0 + MOD - rhs.0;
        if d >= MOD {
            d -= MOD;
        }
        ModInt(d)
    }
}

impl std::ops::SubAssign for ModInt {
    fn sub_assign(&mut self, rhs: ModInt) {
        *self = *self - rhs;
    }
}

impl std::ops::Mul for ModInt {
    type Output = ModInt;
    fn mul(self, rhs: ModInt) -> Self::Output {
        ModInt((self.0 as u64 * rhs.0 as u64 % MOD as u64) as u32)
    }
}

impl std::ops::MulAssign for ModInt {
    fn mul_assign(&mut self, rhs: ModInt) {
        *self = *self * rhs;
    }
}

impl std::ops::Neg for ModInt {
    type Output = ModInt;
    fn neg(self) -> Self::Output {
        ModInt(if self.0 == 0 {0} else {MOD - self.0})
    }
}

impl std::fmt::Display for ModInt {
    fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl std::str::FromStr for ModInt {
    type Err = std::num::ParseIntError;
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let val = s.parse::<u32>()?;
        Ok(ModInt::new(val))
    }
}

#[allow(dead_code)]
impl ModInt {
    pub fn new(n: u32) -> ModInt {
        ModInt(n % MOD)
    }
    pub fn zero() -> ModInt {
        ModInt(0)
    }
    pub fn one() -> ModInt {
        ModInt(1)
    }
    pub fn pow(self, mut n: u32) -> ModInt {
        let mut t = ModInt::one();
        let mut s = self;
        while n > 0 {
            if n & 1 == 1 {
                t *= s;
            }
            s *= s;
            n >>= 1;
        }
        t
    }
    pub fn inv(self) -> ModInt {
        assert!(self.0 > 0);
        self.pow(MOD - 2)
    }
}
// ---------- end ModInt ----------
// ---------- begin Precalc ----------
#[allow(dead_code)]
struct Precalc {
    inv: Vec<ModInt>,
    fact: Vec<ModInt>,
    ifact: Vec<ModInt>,
}

#[allow(dead_code)]
impl Precalc {
    pub fn new(n: usize) -> Precalc {
        let mut inv = vec![ModInt::one(); n + 1];
        let mut fact = vec![ModInt::one(); n + 1];
        let mut ifact = vec![ModInt::one(); n + 1];
        for i in 2..(n + 1) {
            inv[i] = -inv[MOD as usize % i] * ModInt(MOD / i as u32);
            fact[i] = fact[i - 1] * ModInt(i as u32);
            ifact[i] = ifact[i - 1] * inv[i];
        }
        Precalc {
            inv: inv,
            fact: fact,
            ifact: ifact,
        }
    }
    pub fn inv(&self, n: usize) -> ModInt {
        self.inv[n]
    }
    pub fn fact(&self, n: usize) -> ModInt {
        self.fact[n]
    }
    pub fn ifact(&self, n: usize) -> ModInt {
        self.ifact[n]
    }
    pub fn comb(&self, n: usize, k: usize) -> ModInt {
        if k > n {
            return ModInt::zero();
        }
        self.fact[n] * self.ifact[k] * self.ifact[n - k]
    }
}
// ---------- end Precalc ----------
// ---------- begin Link-Cut Tree Lazy ----------
use std::cell::*;
use std::rc::*;

trait TE {
    type T: Clone;
    type E: Clone;
    fn fold(l: &Self::T, r: &Self::T) -> Self::T;
    fn eval(x: &Self::T, f: &Self::E) -> Self::T;
    fn merge(g: &Self::E, h: &Self::E) -> Self::E;
    fn e() -> Self::T;
    fn id() -> Self::E;
}

type Ref<R> = Rc<RefCell<Node<R>>>;
type WeakRef<R> = Weak<RefCell<Node<R>>>;
type Link<R> = Option<Ref<R>>;
type WeakLink<R> = Option<WeakRef<R>>;

#[derive(PartialEq, Eq, Clone, Copy, Debug)]
enum Label {
    Root,
    Left,
    Right,
}

struct Node<R: TE> {
    label: Label,
    rev: bool,
    val: R::T,
    laz: R::E,
    sum: R::T,
    size: usize,
    parent: WeakLink<R>,
    left: Link<R>,
    right: Link<R>,
}

impl<R: TE> Node<R> {
    fn get_size(node: &Link<R>) -> usize {
        node.as_ref().map_or(0, |t| t.borrow().size)
    }

    fn get_sum(node: &Link<R>) -> R::T {
        node.as_ref().map_or(R::e(), |t| {
            let po = t.borrow();
            R::eval(&po.sum, &po.laz)
        })
    }

    fn get_label(node: &Ref<R>) -> Label {
        node.borrow().label
    }

    fn assign_label(node: &Link<R>, label: Label) {
        if let Some(node) = node.as_ref() {
            node.borrow_mut().label = label;
        }
    }

    fn apply(t: &Link<R>, laz: &R::E) {
        if let Some(p) = t.as_ref() {
            let mut po = p.borrow_mut();
            po.laz = R::merge(&po.laz, laz);
        }
    }

    fn push(t: &Ref<R>) {
        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;
        }
        Node::apply(&t_mut.left, &t_mut.laz);
        Node::apply(&t_mut.right, &t_mut.laz);
        t_mut.sum = R::eval(&t_mut.sum, &t_mut.laz);
        t_mut.val = R::eval(&t_mut.val, &t_mut.laz);
        t_mut.laz = R::id();
    }

    fn update(node: &Ref<R>) {
        let mut po = node.borrow_mut();
        po.size = 1 + Node::get_size(&po.left) + Node::get_size(&po.right);
        po.sum = R::fold(&Node::get_sum(&po.left), &R::fold(&po.val, &Node::get_sum(&po.right)));
    }

    fn left_rotate(t: &Ref<R>) {
        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());
            }
        }
        Node::update(&parent);
        Node::update(t);
    }

    fn right_rotate(t: &Ref<R>) {
        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());
            }
        }
        Node::update(&parent);
        Node::update(t);
    }

    fn splay(t: &Ref<R>) {
        Node::push(t);
        while Node::get_label(t) != Label::Root {
            let p = t.borrow().parent.clone().unwrap().upgrade().unwrap();
            if Node::get_label(&p) == Label::Root {
                Node::push(&p);
                Node::push(t);
                let label = Node::get_label(t);
                match label {
                    Label::Left => Node::right_rotate(t),
                    Label::Right => Node::left_rotate(t),
                    _ => unreachable!(),
                }
            } else {
                let q = p.borrow().parent.clone().unwrap().upgrade().unwrap();
                Node::push(&q);
                Node::push(&p);
                Node::push(t);
                let x = Node::get_label(&p);
                let y = Node::get_label(t);
                match (x, y) {
                    (Label::Left, Label::Left) => {
                        Node::right_rotate(&p);
                        Node::right_rotate(t);
                    }
                    (Label::Left, Label::Right) => {
                        Node::left_rotate(t);
                        Node::right_rotate(t);
                    }
                    (Label::Right, Label::Left) => {
                        Node::right_rotate(t);
                        Node::left_rotate(t);
                    }
                    (Label::Right, Label::Right) => {
                        Node::left_rotate(&p);
                        Node::left_rotate(t);
                    }
                    _ => unreachable!(),
                }
            }
        }
    }

    fn expose(x: &Ref<R>) {
        let mut rp: Link<R> = None;
        let mut cur = x.clone();
        loop {
            Node::splay(&cur);
            Node::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;
            Node::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;
            }
        }
        Node::splay(x);
    }

    #[allow(dead_code)]
    fn cut(c: &Ref<R>) {
        Node::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;
        Node::update(c);
    }

    fn link(c: &Ref<R>, p: &Ref<R>) {
        Node::expose(c);
        Node::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());
        Node::update(p);
    }

    fn evert(v: &Ref<R>) {
        Node::expose(v);
        v.borrow_mut().rev ^= true;
    }
}

struct LinkCutTree<R: TE> {
    node: Vec<Ref<R>>,
}

impl<R: TE> LinkCutTree<R> {
    fn build_by(a: &[R::T]) -> Self {
        let mut node = Vec::with_capacity(a.len());
        for a in a.iter() {
            let t = Rc::new(RefCell::new(Node::<R> {
                label: Label::Root,
                rev: false,
                val: a.clone(),
                laz: R::id(),
                sum: a.clone(),
                size: 1,
                parent: None,
                left: None,
                right: None,
            }));
            node.push(t);
        }
        LinkCutTree {
            node: node,
        }
    }
    #[allow(dead_code)]
    fn cut(&self, a: usize, b: usize,) {
        self.evert(a);
        Node::cut(&self.node[b]);
    }
    fn link(&self, c: usize, p: usize) {
        self.evert(c);
        Node::link(&self.node[c], &self.node[p]);
    }
    fn expose(&self, v: usize) {
        Node::expose(&self.node[v]);
    }
    fn evert(&self, v: usize) {
        Node::evert(&self.node[v]);
    }
    fn find(&self, src: usize, dst: usize) -> R::T {
        self.evert(src);
        self.expose(dst);
        self.node[dst].borrow().sum.clone()
    }
    fn update(&mut self, src: usize, dst: usize, laz: R::E) {
        self.evert(src);
        self.expose(dst);
        self.node[dst].borrow_mut().laz = laz;
    }
}
// ---------- end Link-Cut Tree Lazy ----------

struct R;
impl TE for R {
    type T = (ModInt, ModInt);
    type E = ModInt;
    fn fold(l: &Self::T, r: &Self::T) -> Self::T {
        (l.0 + r.0, l.1 + r.1)
    }
    fn eval(x: &Self::T, f: &Self::E) -> Self::T {
        (x.0 + x.1 * *f, x.1)
    }
    fn merge(g: &Self::E, h: &Self::E) -> Self::E {
        *g + *h
    }
    fn e() -> Self::T {
        (ModInt::zero(), ModInt::zero())
    }
    fn id() -> Self::E {
        ModInt::zero()
    }
}

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 mut a = vec![(ModInt::zero(), ModInt::zero()); n];
    for a in a.iter_mut() {
        a.0 = it.next().unwrap().parse().unwrap();
    }
    for a in a.iter_mut() {
        a.1 = it.next().unwrap().parse().unwrap();
    }
    let mut lct = LinkCutTree::<R>::build_by(&a);
    for _ in 1..n {
        let a: usize = it.next().unwrap().parse().unwrap();
        let b: usize = it.next().unwrap().parse().unwrap();
        lct.link(a - 1, b - 1);
    }
    let q: usize = it.next().unwrap().parse().unwrap();
    for _ in 0..q {
        let op: usize = it.next().unwrap().parse().unwrap();
        if op == 0 {
            let x: usize = it.next().unwrap().parse().unwrap();
            let y: usize = it.next().unwrap().parse().unwrap();
            let z: ModInt = it.next().unwrap().parse().unwrap();
            lct.update(x - 1, y - 1, z);
        } else {
            let x: usize = it.next().unwrap().parse().unwrap();
            let y: usize = it.next().unwrap().parse().unwrap();
            let ans = lct.find(x - 1, y - 1);
            writeln!(out, "{}", ans.0).ok();
        }
    }
}

fn main() {
    run();
}