fn main() { let mut io = IO::new(); input!{ from io, n: usize, ed:[(usize, usize); n-1], tax: [i64; n], q: usize, query: [(usize, usize, i64); q], } let mut hld = HeavyLightDecomposition::new(n); for &(u, v) in &ed { hld.add_edge(u, v); } hld.build(0); let mut tt = vec![0; n+1]; for v in 0..n { tt[hld.id(v) + 1] = tax[v]; } for i in 0..n { tt[i+1] += tt[i]; } let mut ans = 0; for &(u, v, c) in &query { let (rl, lr) = hld.for_each_vertex(u, v); let mut cur = 0; for rng in rl.into_iter().chain(lr) { let l = rng.start; let r = rng.end; cur += tt[r] - tt[l]; } ans += cur * c; } io.println(ans); } // ------------ Heavy Light Decomposition start ------------ use std::ops::Range; pub struct HeavyLightDecomposition { graph: Vec>, index: Vec, // 新しい頂点番号 parent: Vec, // 親 head: Vec, // 属するHeavy Pathの根 range: Vec, // 部分木の開区間右端 } impl HeavyLightDecomposition { pub fn new(n: usize) -> Self { Self { graph: vec![Vec::new(); n], index: Vec::new(), parent: Vec::new(), head: Vec::new(), range: Vec::new(), } } pub fn add_edge(&mut self, u: usize, v: usize) { self.graph[u].push(v); self.graph[v].push(u); } pub fn build(&mut self, root: usize) { let graph = &mut self.graph; let n = graph.len(); let mut index = vec![0; n]; let mut parent = vec![n; n]; let mut head = vec![root; n]; let mut range = vec![0; n]; let mut siz = vec![1; n]; let mut st = Vec::new(); st.push(root); while let Some(v) = st.pop() { if v < n { st.push(!v); if let Some(k) = graph[v].iter().position(|&u| u == parent[v]) { graph[v].swap_remove(k); } graph[v].iter().for_each(|&u| { parent[u] = v; st.push(u); }); } else { let v = !v; for i in 0..graph[v].len() { let u = graph[v][i]; siz[v] += siz[u]; if siz[graph[v][0]] < siz[u] { graph[v].swap(0, i); } } } } st.push(root); let mut c = 0; while let Some(v) = st.pop() { if v < n { st.push(!v); index[v] = c; c += 1; for &u in graph[v].iter().skip(1) { head[u] = u; st.push(u); } if let Some(&u) = graph[v].get(0) { head[u] = head[v]; st.push(u); } } else { range[!v] = c; } } self.index = index; self.parent = parent; self.head = head; self.range = range; } pub fn lca(&self, mut u: usize, mut v: usize) -> usize { let parent = &self.parent; let head = &self.head; let index = &self.index; while head[u] != head[v] { if index[u] < index[v] { v = parent[head[v]]; } else { u = parent[head[u]]; } } if index[u] < index[v] { u } else { v } } fn for_each(&self, mut u: usize, mut v: usize, b: usize) -> (Vec>, Vec>) { let parent = &self.parent; let head = &self.head; let index = &self.index; let mut up = Vec::new(); let mut down = Vec::new(); while head[u] != head[v] { if index[u] < index[v] { let h = head[v]; down.push(index[h]..index[v] + 1); v = parent[h]; } else { let h = head[u]; up.push(index[h]..index[u] + 1); u = parent[h]; } } if index[u] < index[v] { down.push(index[u] + b .. index[v] + 1); } else if index[v] + b < index[u] + 1 { up.push(index[v] + b .. index[u] + 1); } down.reverse(); (up, down) } pub fn id(&self, v: usize) -> usize { self.index[v] } pub fn for_each_vertex(&self, u: usize, v: usize) -> (Vec>, Vec>) { self.for_each(u, v, 0) } pub fn for_each_edge(&self, u: usize, v: usize) -> (Vec>, Vec>) { self.for_each(u, v, 1) } pub fn subtree_range(&self, v: usize) -> Range { self.index[v]..self.range[v] } } // ------------ Heavy Light Decomposition end ------------ // ------------ io module start ------------ use std::io::{stdout, BufWriter, Read, StdoutLock, Write}; pub struct IO { iter: std::str::SplitAsciiWhitespace<'static>, buf: BufWriter>, } impl IO { pub fn new() -> Self { let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); let input = Box::leak(input.into_boxed_str()); let out = Box::new(stdout()); IO { iter: input.split_ascii_whitespace(), buf: BufWriter::new(Box::leak(out).lock()), } } fn scan_str(&mut self) -> &'static str { self.iter.next().unwrap() } pub fn scan(&mut self) -> ::Output { ::scan(self) } pub fn scan_vec(&mut self, n: usize) -> Vec<::Output> { (0..n).map(|_| self.scan::()).collect() } pub fn print(&mut self, x: T) { ::print(self, x); } pub fn println(&mut self, x: T) { self.print(x); self.print("\n"); } pub fn iterln>(&mut self, mut iter: I, delim: &str) { if let Some(v) = iter.next() { self.print(v); for v in iter { self.print(delim); self.print(v); } } self.print("\n"); } pub fn flush(&mut self) { self.buf.flush().unwrap(); } } impl Default for IO { fn default() -> Self { Self::new() } } pub trait Scan { type Output; fn scan(io: &mut IO) -> Self::Output; } macro_rules! impl_scan { ($($t:tt),*) => { $( impl Scan for $t { type Output = Self; fn scan(s: &mut IO) -> Self::Output { s.scan_str().parse().unwrap() } } )* }; } impl_scan!(i16, i32, i64, isize, u16, u32, u64, usize, String, f32, f64); pub enum Bytes {} impl Scan for Bytes { type Output = &'static [u8]; fn scan(s: &mut IO) -> Self::Output { s.scan_str().as_bytes() } } pub enum Chars {} impl Scan for Chars { type Output = Vec; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().collect() } } pub enum Usize1 {} impl Scan for Usize1 { type Output = usize; fn scan(s: &mut IO) -> Self::Output { s.scan::().wrapping_sub(1) } } impl Scan for (T, U) { type Output = (T::Output, U::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s)) } } impl Scan for (T, U, V) { type Output = (T::Output, U::Output, V::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s)) } } impl Scan for (T, U, V, W) { type Output = (T::Output, U::Output, V::Output, W::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s), W::scan(s)) } } pub trait Print { fn print(w: &mut IO, x: Self); } macro_rules! impl_print_int { ($($t:ty),*) => { $( impl Print for $t { fn print(w: &mut IO, x: Self) { w.buf.write_all(x.to_string().as_bytes()).unwrap(); } } )* }; } impl_print_int!(i16, i32, i64, isize, u16, u32, u64, usize, f32, f64); impl Print for u8 { fn print(w: &mut IO, x: Self) { w.buf.write_all(&[x]).unwrap(); } } impl Print for &[u8] { fn print(w: &mut IO, x: Self) { w.buf.write_all(x).unwrap(); } } impl Print for &str { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for String { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for (T, U) { fn print(w: &mut IO, (x, y): Self) { w.print(x); w.print(" "); w.print(y); } } impl Print for (T, U, V) { fn print(w: &mut IO, (x, y, z): Self) { w.print(x); w.print(" "); w.print(y); w.print(" "); w.print(z); } } mod neboccoio_macro { #[macro_export] macro_rules! input { (@start $io:tt @read @rest) => {}; (@start $io:tt @read @rest, $($rest: tt)*) => { input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @rest mut $($rest:tt)*) => { input!(@start $io @read @mut [mut] @rest $($rest)*) }; (@start $io:tt @read @rest $($rest:tt)*) => { input!(@start $io @read @mut [] @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [$kind:tt; $len:expr] $($rest:tt)*) => { let $($mut)* $var = $io.scan_vec::<$kind>($len); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: $kind:tt $($rest:tt)*) => { let $($mut)* $var = $io.scan::<$kind>(); input!(@start $io @read @rest $($rest)*) }; (from $io:tt $($rest:tt)*) => { input!(@start $io @read @rest $($rest)*) }; } } // ------------ io module end ------------