// Bundled at 2022/07/29 18:18:48 +09:00 // Author: Haar pub mod main { use super::*; use haar_lib::{ ds::lazy_segtree_coeff::*, get, input, io, math::ff::{modint::*, *}, modulo, sort_with, tree::{hld::*, *}, utils::join_str::*, }; use std::io::Write; #[derive(Clone, Default)] pub struct Problem {} modulo!(M, 1000000007); type Mint = ModInt; impl Problem { pub fn main(&mut self) -> Result<(), Box> { io!(cin, cout); input ! (cin , n : usize , mut s : [Mint ; n] , mut c : [Mint ; n]); let mut tree = Tree::new(n); tree.add_undirected((0..n - 1).map(|_| { input!(cin, a: usize, b: usize); (a - 1, b - 1, ()) })); let hld = HLD::new(tree, 0); sort_with!(|&i, &j| hld.get_id(i).cmp(&hld.get_id(j)), s, c); let mut seg = LazySegmentTreeCoeff::new(n, c); seg.init_with_vec(s); input!(cin, q: usize); for _ in 0..q { input!(cin, t: usize); match t { 0 => { input!(cin, x: usize, y: usize, z: Mint); for (l, r) in hld.path_query_vertex(x - 1, y - 1) { seg.update(l..r, z); } } 1 => { input!(cin, x: usize, y: usize); let mut ans = Mint::from(0); for (l, r) in hld.path_query_vertex(x - 1, y - 1) { ans += seg.fold(l..r); } writeln!(cout, "{}", ans)?; } _ => unreachable!(), } } Ok(()) } } } fn main() { main::Problem::default().main().unwrap(); } use crate as haar_lib; pub mod algebra { pub mod one_zero { pub trait Zero { type Output; fn zero() -> Self::Output; } pub trait One { type Output; fn one() -> Self::Output; } macro_rules! impl_one_zero { ($($t:ty),*) => { $( impl Zero for $t { type Output = $t; fn zero() -> Self::Output { 0 as $t } } impl One for $t { type Output = $t; fn one() -> Self::Output { 1 as $t } } )* } } impl_one_zero!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize, f32, f64); } } pub mod ds { pub mod traits { pub trait Foldable { type Output; fn fold(&self, range: Idx) -> Self::Output; } pub trait Assignable { type Value; fn assign(&mut self, i: Idx, value: Self::Value); } pub trait Updatable { type Value; fn update(&mut self, i: Idx, value: Self::Value); } pub trait Indexable { type Output; fn get(&self, i: Idx) -> Self::Output; } } pub mod lazy_segtree_coeff { pub use crate::ds::traits::Updatable; use std::ops::{Add, Mul, Range}; use std::cell::Cell; pub struct LazySegmentTreeCoeff { size: usize, data: Vec, lazy: Vec, coeff: Vec, } impl LazySegmentTreeCoeff where T: Copy + Default + Add + Mul + PartialEq, { pub fn new(n: usize, coefficients: Vec) -> Self { let size = n.next_power_of_two() * 2; let mut coeff = vec![T::default(); size]; for i in 0..coefficients.len() { coeff[i + size / 2] = coefficients[i]; } for i in (1..size / 2).rev() { coeff[i] = coeff[i << 1] + coeff[i << 1 | 1]; } Self { size, data: vec![T::default(); size], lazy: vec![T::default(); size], coeff, } } pub fn init_with_vec(&mut self, value: Vec) { self.data = vec![T::default(); self.size]; self.lazy = vec![T::default(); self.size]; for (i, x) in value.into_iter().enumerate() { self.data[self.size / 2 + i] = x; } for i in (1..self.size / 2).rev() { self.data[i] = self.data[i << 1] + self.data[i << 1 | 1]; } } fn propagate(&mut self, i: usize) { if self.lazy[i] != T::default() { if i < self.size / 2 { self.lazy[i << 1] = self.lazy[i] + self.lazy[i << 1]; self.lazy[i << 1 | 1] = self.lazy[i] + self.lazy[i << 1 | 1]; } self.data[i] = self.data[i] + self.lazy[i] * self.coeff[i]; self.lazy[i] = T::default(); } } fn update_internal( &mut self, i: usize, l: usize, r: usize, s: usize, t: usize, value: T, ) -> T { self.propagate(i); if r <= s || t <= l { return self.data[i]; } if s <= l && r <= t { self.lazy[i] = self.lazy[i] + value; self.propagate(i); return self.data[i]; } self.data[i] = self.update_internal(i << 1, l, (l + r) / 2, s, t, value) + self.update_internal(i << 1 | 1, (l + r) / 2, r, s, t, value); self.data[i] } fn get_internal(&mut self, i: usize, l: usize, r: usize, x: usize, y: usize) -> T { self.propagate(i); if r <= x || y <= l { return T::default(); } if x <= l && r <= y { return self.data[i]; } self.get_internal(i << 1, l, (l + r) / 2, x, y) + self.get_internal(i << 1 | 1, (l + r) / 2, r, x, y) } pub fn fold(&mut self, Range { start, end }: Range) -> T { self.get_internal(1, 0, self.size / 2, start, end) } } impl Updatable> for LazySegmentTreeCoeff where T: Copy + Default + Add + Mul + PartialEq, { type Value = T; fn update(&mut self, Range { start, end }: Range, value: T) { self.update_internal(1, 0, self.size / 2, start, end, value); } } } } pub mod macros { pub mod io { #[macro_export] macro_rules! get { ( $in:ident, [$a:tt; $num:expr] ) => { { let n = $num; (0 .. n).map(|_| get!($in, $a)).collect::>() } }; ( $in:ident, ($($type:ty),*) ) => { ($(get!($in, $type)),*) }; ( $in:ident, $type:ty ) => { { let token = $in.next().unwrap(); token.parse::<$type>().expect( format!("cannot convert \"{}\" into {}", token, stringify!($type)).as_str() ) } }; } #[macro_export] macro_rules! input { ( @inner $in:ident, mut $name:ident : $type:tt ) => { let mut $name = get!($in, $type); }; ( @inner $in:ident, $name:ident : $type:tt ) => { let $name = get!($in, $type); }; ( $in:ident, $($($names:ident)* : $type:tt),* ) => { $( input!(@inner $in, $($names)* : $type); )* } } #[macro_export] macro_rules! io { ( $in:ident, $out:ident ) => { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut $in = s.split_ascii_whitespace(); let $out = std::io::stdout(); let mut $out = std::io::BufWriter::new($out.lock()); }; } } pub mod modulo { #[macro_export] macro_rules! modulo { ($name:ident, $m:expr) => { #[derive(Debug, Copy, Clone, PartialEq, Eq, Default)] struct $name {} impl Modulo for $name { #[inline] fn value() -> u32 { $m } } }; } } pub mod sort_with { #[macro_export] macro_rules! sort_with { ($cmp:expr, $($a:expr),+) => { { let n = vec![$($a.len()),+].into_iter().min().unwrap(); let mut ord = (0..n).collect::>(); ord.sort_by($cmp); let mut check = vec![false; n]; for i in 0..n { if !check[i] { check[i] = true; let mut j = i; while ord[j] != i { { $( $a.swap(j, ord[j]); )+ } j = ord[j]; check[j] = true; } } } } } } } } pub mod math { pub mod ff { pub mod modint { pub use crate::{ algebra::one_zero::{One, Zero}, math::ff::traits::{Frac, Inv, Pow, FF}, }; use std::{ fmt, fmt::{Debug, Display, Formatter}, iter::Sum, marker::PhantomData, num::ParseIntError, ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign}, str::FromStr, }; pub trait Modulo { fn value() -> u32; } #[derive(Copy, Clone, PartialEq, Default)] pub struct ModInt { value: u32, phantom: PhantomData, } impl FF for ModInt {} impl ModInt { pub fn new(n: u32) -> Self { Self { value: if n < M::value() { n } else { n % M::value() }, phantom: PhantomData, } } #[inline] fn new_unchecked(value: u32) -> Self { Self { value, phantom: PhantomData, } } #[inline] fn add_internal(self, other: Self) -> Self { let a = self.value + other.value; Self::new_unchecked(if a < M::value() { a } else { a - M::value() }) } #[inline] fn sub_internal(self, other: Self) -> Self { let a = if self.value < other.value { self.value + M::value() - other.value } else { self.value - other.value }; Self::new_unchecked(a) } #[inline] fn mul_internal(self, other: Self) -> Self { let a = self.value as u64 * other.value as u64; Self::new_unchecked(if a < M::value() as u64 { a as u32 } else { (a % M::value() as u64) as u32 }) } #[inline] fn div_internal(self, other: Self) -> Self { self * other.inv_internal() } #[inline] fn inv_internal(self) -> Self { self.pow_internal(M::value() as u64 - 2) } #[inline] fn pow_internal(self, mut p: u64) -> Self { let mut ret: u64 = 1; let mut a = self.value as u64; while p > 0 { if (p & 1) != 0 { ret *= a; ret %= M::value() as u64; } a *= a; a %= M::value() as u64; p >>= 1; } Self::new_unchecked(ret as u32) } } impl Pow for ModInt { type Output = Self; fn pow(self, p: u64) -> Self { self.pow_internal(p) } } impl Inv for ModInt { type Output = Self; fn inv(self) -> Self { self.inv_internal() } } impl Frac for ModInt { type Output = Self; fn frac(numerator: i64, denominator: i64) -> Self { Self::from(numerator) * Self::from(denominator).inv() } } impl Display for ModInt { fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { write!(f, "{}", self.value) } } impl Debug for ModInt { fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { write!(f, "{} (mod {})", self.value, M::value()) } } macro_rules! modint_from_int { ( $($t:ty),* ) => { $( impl From<$t> for ModInt { fn from(from: $t) -> Self { let mut value = ((from % M::value() as $t) + M::value() as $t) as u32; if value >= M::value() { value -= M::value(); } Self::new_unchecked(value) } } )* } } modint_from_int!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize); impl From> for u32 { fn from(from: ModInt) -> Self { from.value } } macro_rules! impl_modint_arith { ($tr:ident, $f:ident, $fi:ident, $tr_a:ident, $f_a:ident, $op:tt) => { impl $tr for ModInt { type Output = Self; #[inline] fn $f(self, other: Self) -> Self { self.$fi(other) } } impl $tr_a for ModInt { #[inline] fn $f_a(&mut self, other: Self) { *self = *self $op other; } } } } impl_modint_arith ! (Add , add , add_internal , AddAssign , add_assign , +) ; impl_modint_arith ! (Sub , sub , sub_internal , SubAssign , sub_assign , -) ; impl_modint_arith ! (Mul , mul , mul_internal , MulAssign , mul_assign , *) ; impl_modint_arith ! (Div , div , div_internal , DivAssign , div_assign , /) ; impl Neg for ModInt { type Output = Self; fn neg(self) -> Self { Self::new_unchecked(if self.value == 0 { 0 } else { M::value() - self.value }) } } impl FromStr for ModInt { type Err = ParseIntError; fn from_str(s: &str) -> Result { let x = s.parse::()?; Ok(Self::from(x)) } } impl Sum for ModInt { fn sum>(iter: I) -> Self { iter.fold(Self::new_unchecked(0), |a, b| a + b) } } impl Zero for ModInt { type Output = Self; #[inline] fn zero() -> Self::Output { Self::new_unchecked(0) } } impl One for ModInt { type Output = Self; #[inline] fn one() -> Self::Output { Self::new_unchecked(1) } } } pub mod traits { use std::{ iter::Sum, ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign}, }; pub trait Pow { type Output; fn pow(self, p: u64) -> Self::Output; } pub trait Inv { type Output; fn inv(self) -> Self::Output; } pub trait Frac { type Output; fn frac(_: i64, _: i64) -> Self::Output; } pub trait FF: Pow + Inv + Frac + Add + AddAssign + Sub + SubAssign + Mul + MulAssign + Div + DivAssign + Neg + Sum + Copy + Clone + PartialEq + Default + Sized { } } } } pub mod tree { pub mod hld { use crate::tree::*; use std::cmp::max; #[derive(Clone, Debug)] pub struct HLD { size: usize, par: Vec>, head: Vec, id: Vec, rid: Vec, next: Vec>, end: Vec, } impl HLD { pub fn new(tree: Tree, root: usize) -> Self { let size = tree.len(); let mut ret = Self { size, par: vec![None; size], head: vec![0; size], id: vec![0; size], rid: vec![0; size], next: vec![None; size], end: vec![0; size], }; let mut tr = vec![vec![]; size]; for (i, edges) in tree.nodes.iter().enumerate() { for &TreeEdge { to, .. } in edges.neighbors() { tr[i].push(to); } } ret.dfs_sub(&mut tr, root, None, &mut vec![1; size]); ret.dfs_build(&tr, root, &mut 0); ret } fn dfs_sub( &mut self, tree: &mut [Vec], cur: usize, par: Option, sub: &mut Vec, ) { self.par[cur] = par; tree[cur].retain(|&x| Some(x) != par); let mut t = 0; let n = tree[cur].len(); for i in 0..n { let to = tree[cur][i]; self.dfs_sub(tree, to, Some(cur), sub); sub[cur] += sub[to]; if sub[to] > t { t = sub[to]; self.next[cur] = Some(to); tree[cur].swap(i, 0); } } } fn dfs_build(&mut self, tree: &[Vec], cur: usize, index: &mut usize) { self.id[cur] = *index; self.rid[*index] = cur; *index += 1; for (i, &to) in tree[cur].iter().enumerate() { self.head[to] = if i == 0 { self.head[cur] } else { to }; self.dfs_build(tree, to, index); } self.end[cur] = *index; } pub fn path_query_vertex(&self, mut x: usize, mut y: usize) -> Vec<(usize, usize)> { let mut ret = vec![]; loop { if self.id[x] > self.id[y] { std::mem::swap(&mut x, &mut y); } ret.push((max(self.id[self.head[y]], self.id[x]), self.id[y] + 1)); if self.head[x] == self.head[y] { break; } y = self.par[self.head[y]].unwrap(); } ret } pub fn path_query_edge(&self, mut x: usize, mut y: usize) -> Vec<(usize, usize)> { let mut ret = vec![]; loop { if self.id[x] > self.id[y] { std::mem::swap(&mut x, &mut y); } if self.head[x] == self.head[y] { if x != y { ret.push((self.id[x] + 1, self.id[y] + 1)); } break; } ret.push((self.id[self.head[y]], self.id[y] + 1)); y = self.par[self.head[y]].unwrap(); } ret } pub fn subtree_query_vertex(&self, x: usize) -> (usize, usize) { (self.id[x], self.end[x]) } pub fn subtree_query_edge(&self, x: usize) -> (usize, usize) { (self.id[x] + 1, self.end[x]) } pub fn parent(&self, x: usize) -> Option { self.par[x] } pub fn get_id(&self, x: usize) -> usize { self.id[x] } pub fn lca(&self, mut u: usize, mut v: usize) -> usize { loop { if self.id[u] > self.id[v] { std::mem::swap(&mut u, &mut v); } if self.head[u] == self.head[v] { return u; } v = self.par[self.head[v]].unwrap(); } } } } #[derive(Clone, Debug)] pub struct TreeEdge { pub to: usize, pub weight: T, } #[derive(Clone, Debug)] pub struct TreeNode { pub index: usize, pub parent: Option>, pub children: Vec>, } #[derive(Clone, Debug)] pub struct Tree { pub nodes: Vec>, } impl TreeNode { pub fn neighbors(&self) -> impl DoubleEndedIterator> { self.children.iter().chain(self.parent.iter()) } pub fn neighbors_size(&self) -> usize { self.children.len() + self.parent.as_ref().map_or(0, |_| 1) } } impl Tree { pub fn new(size: usize) -> Self { Self { nodes: (0..size) .map(|i| TreeNode { index: i, parent: None, children: vec![], }) .collect(), } } pub fn add_undirected(&mut self, edges: impl IntoIterator) { for (u, v, w) in edges { self.nodes[u].children.push(TreeEdge { to: v, weight: w }); self.nodes[v].children.push(TreeEdge { to: u, weight: w }); } } pub fn add_directed(&mut self, edges: impl IntoIterator) { for (p, c, w) in edges { assert!(self.nodes[c].parent.is_none()); self.nodes[p].children.push(TreeEdge { to: c, weight: w }); self.nodes[c].parent = Some(TreeEdge { to: p, weight: w }); } } } impl Tree { pub fn len(&self) -> usize { self.nodes.len() } pub fn is_empty(&self) -> bool { self.nodes.is_empty() } } } pub mod utils { pub mod join_str { pub trait JoinStr { fn join_str(self, _: &str) -> String; } impl JoinStr for I where T: ToString, I: Iterator, { fn join_str(self, s: &str) -> String { self.map(|x| x.to_string()).collect::>().join(s) } } } }