// ---------- 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 { let val = s.parse::()?; 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, fact: Vec, ifact: Vec, } #[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 = Rc>>; type WeakRef = Weak>>; type Link = Option>; type WeakLink = Option>; #[derive(PartialEq, Eq, Clone, Copy, Debug)] enum Label { Root, Left, Right, } struct Node { label: Label, rev: bool, val: R::T, laz: R::E, sum: R::T, size: usize, parent: WeakLink, left: Link, right: Link, } impl Node { fn get_size(node: &Link) -> usize { node.as_ref().map_or(0, |t| t.borrow().size) } fn get_sum(node: &Link) -> 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) -> Label { node.borrow().label } fn assign_label(node: &Link, label: Label) { if let Some(node) = node.as_ref() { node.borrow_mut().label = label; } } fn apply(t: &Link, 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) { 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) { 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) { 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) { 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) { 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) { let mut rp: Link = 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) { 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, p: &Ref) { 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) { Node::expose(v); v.borrow_mut().rev ^= true; } } struct LinkCutTree { node: Vec>, } impl LinkCutTree { 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:: { 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::::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(); }