// ---------- 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(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.0) } } */ #[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 { self.pow(MOD - 2) } } // ---------- end ModInt ---------- // ---------- begin Heavy-Light decomposition ---------- struct HLD { graph: Vec>, path_root: Vec, path_parent: Vec, left: Vec, right: Vec, } #[allow(dead_code)] impl HLD { fn new(n: usize) -> Self { HLD { graph: vec![vec![]; n], path_root: vec![], path_parent: vec![], left: vec![], right: vec![], } } fn add_edge(&mut self, a: usize, b: usize) { self.graph[a].push(b); self.graph[b].push(a); } fn build(&mut self, root: usize) { let mut q = vec![]; let mut stack = vec![(root, root)]; let graph = &mut self.graph; while let Some((v, p)) = stack.pop() { q.push(v); for i in 0..graph[v].len() { if graph[v][i] == p { graph[v].swap_remove(i); break; } } for &u in &graph[v] { stack.push((u, v)); } } let n = graph.len(); let mut size = vec![1; n]; for &v in q.iter().rev() { for i in 0..graph[v].len() { let u = graph[v][i]; size[v] += size[u]; if size[u] > size[graph[v][0]] { graph[v].swap(0, i); } } } let mut path_root = vec![root; n]; let mut path_parent = vec![root; n]; let mut left = vec![0; n]; let mut right = vec![0; n]; let mut stack = vec![(root, 0)]; let mut k = 0; while let Some((v, op)) = stack.pop() { if op == 1 { right[v] = k; continue; } left[v] = k; k += 1; stack.push((v, 1)); for i in 1..graph[v].len() { let u = graph[v][i]; path_root[u] = u; path_parent[u] = v; stack.push((u, 0)); } if graph[v].len() > 0 { let u = graph[v][0]; path_root[u] = path_root[v]; path_parent[u] = path_parent[v]; stack.push((u, 0)); } } self.path_root = path_root; self.path_parent = path_parent; self.left = left; self.right = right; } fn sub_tree(&self, v: usize) -> (usize, usize) { (self.left[v], self.right[v]) } fn path(&self, v: usize, u: usize) -> Vec<(usize, usize)> { let path = &self.path_root; let parent = &self.path_parent; let index = &self.left; let mut x = v; let mut y = u; let mut ans = vec![]; while path[x] != path[y] { if index[x] < index[y] { let p = path[y]; ans.push((index[p], index[y] + 1)); y = parent[y]; } else { let p = path[x]; ans.push((index[p], index[x] + 1)); x = parent[x]; } } ans.push((std::cmp::min(index[x], index[y]), std::cmp::max(index[x], index[y]) + 1)); ans } } // ---------- end Heavy-Light decomposition ---------- // ---------- begin Lazy Segment Tree ---------- pub 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; } pub struct LazySegmentTree { size: usize, bit: usize, a: Vec<(R::T, R::E)>, } impl LazySegmentTree { pub fn new(n: usize) -> LazySegmentTree { let mut bit = 0; while (1 << bit) < n { bit += 1; } LazySegmentTree { size: 1 << bit, bit: bit, a: vec![(R::e(), R::id()); 2 << bit], } } pub fn build_by(z: &[R::T]) -> LazySegmentTree { let n = z.len(); let mut bit = 0; while (1 << bit) < n { bit += 1; } let mut a = vec![(R::e(), R::id()); 2 << bit]; for (a, z) in a[(1 << bit)..].iter_mut().zip(z.iter()) { a.0 = z.clone(); } for i in (1..(1 << bit)).rev() { let l = R::eval(a[2 * i].0.clone(), a[2 * i].1.clone()); let r = R::eval(a[2 * i + 1].0.clone(), a[2 * i + 1].1.clone()); a[i].0 = R::fold(l, r); } LazySegmentTree { size: 1 << bit, bit : bit, a: a, } } fn eval(&self, k: usize) -> R::T { R::eval(self.a[k].0.clone(), self.a[k].1.clone()) } fn propagate(&mut self, x: usize) { let x = x + self.size; for i in (1..(self.bit + 1)).rev() { let k = x >> i; self.a[2 * k].1 = R::merge(self.a[2 * k].1.clone(), self.a[k].1.clone()); self.a[2 * k + 1].1 = R::merge(self.a[2 * k + 1].1.clone(), self.a[k].1.clone()); self.a[k].1 = R::id(); self.a[k].0 = R::fold(self.eval(2 * k), self.eval(2 * k + 1)); } } fn save(&mut self, x: usize) { let x = x + self.size; for i in 1..(self.bit + 1) { let k = x >> i; self.a[k].0 = R::fold(self.eval(2 * k), self.eval(2 * k + 1)); } } pub fn update(&mut self, l: usize, r: usize, op: R::E) { self.propagate(l); self.propagate(r - 1); let mut x = l + self.size; let mut y = r + self.size; while x < y { if x & 1 == 1 { self.a[x].1 = R::merge(self.a[x].1.clone(), op.clone()); x += 1; } if y & 1 == 1 { y -= 1; self.a[y].1 = R::merge(self.a[y].1.clone(), op.clone()); } x >>= 1; y >>= 1; } self.save(l); self.save(r - 1); } pub fn find(&mut self, l: usize, r: usize) -> R::T { self.propagate(l); self.propagate(r - 1); let mut x = l + self.size; let mut y = r + self.size; let mut p = R::e(); let mut q = R::e(); while x < y { if x & 1 == 1 { p = R::fold(p, self.eval(x)); x += 1; } if y & 1 == 1 { y -= 1; q = R::fold(self.eval(y), q); } x >>= 1; y >>= 1; } R::fold(p, q) } } // ---------- end Lazy Segment Tree ---------- use std::io::Read; use std::io::Write; 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() } } 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 s: Vec = (0..n).map(|_| ModInt(it.next().unwrap().parse().unwrap())).collect(); let c: Vec = (0..n).map(|_| ModInt(it.next().unwrap().parse().unwrap())).collect(); let mut hld = HLD::new(n); for _ in 1..n { let a = it.next().unwrap().parse::().unwrap() - 1; let b = it.next().unwrap().parse::().unwrap() - 1; hld.add_edge(a, b); } hld.build(0); let mut a = vec![(ModInt::zero(), ModInt::zero()); n]; for i in 0..n { let k = hld.sub_tree(i).0; a[k] = (s[i], c[i]); } let mut s = LazySegmentTree::::build_by(&a); let q: usize = it.next().unwrap().parse().unwrap(); for _ in 0..q { let op: u8 = it.next().unwrap().parse().unwrap(); let x: usize = it.next().unwrap().parse::().unwrap() - 1; let y: usize = it.next().unwrap().parse::().unwrap() - 1; let path = hld.path(x, y); if op == 0 { let z = ModInt(it.next().unwrap().parse().unwrap()); for (l, r) in path { s.update(l, r, z); } } else { let mut ans = ModInt::zero(); for (l, r) in path { ans += s.find(l, r).0; } writeln!(out, "{}", ans.0).ok(); } } } fn main() { run(); }