#[allow(unused_imports)] use std::{ convert::{Infallible, TryFrom, TryInto as _}, fmt::{self, Debug, Display, Formatter,}, fs::File, hash::{Hash, Hasher, BuildHasherDefault}, iter::{Product, Sum}, marker::PhantomData, ops::{Add, AddAssign, Sub, SubAssign, Div, DivAssign, Mul, MulAssign, Neg, RangeBounds, BitAnd, BitAndAssign, BitOr, BitXor, BitXorAssign, BitOrAssign, Index, IndexMut}, str::FromStr, sync::{atomic::{self, AtomicU32, AtomicU64}, Once}, collections::{*, btree_set::Range, btree_map::Range as BTreeRange}, mem::{take, swap}, cmp::{self, Reverse, Ordering, Eq, PartialEq, PartialOrd}, thread::LocalKey, f64::consts::PI, time::Instant, cell::RefCell, io::{self, stdin, Read, read_to_string, BufWriter, BufReader, stdout, Write}, ptr::null_mut, println, print,debug_assert,debug_assert_eq,debug_assert_ne, matches }; #[allow(unused_imports)] use core::panic; pub mod fxhash { use std::hash::BuildHasherDefault; const K: u64 = 0x517c_c1b7_2722_0a95; #[derive(Default)] pub struct FxHasher { pub hash: u64, } impl FxHasher { #[inline(always)] fn mix_u64(mut h: u64, x: u64) -> u64 { h = h.rotate_left(5) ^ x; h = h.wrapping_mul(K); let x2 = x ^ (x >> 33) ^ (x << 11); h = h.rotate_left(5) ^ x2; h = h.wrapping_mul(K); h } #[inline(always)] fn write_u64_impl(&mut self, x: u64) { self.hash = Self::mix_u64(self.hash, x); } } impl std::hash::Hasher for FxHasher { #[inline(always)] fn finish(&self) -> u64 { self.hash } #[inline(always)] fn write(&mut self, bytes: &[u8]) { let mut h = self.hash; for &b in bytes { h = h.rotate_left(5) ^ (b as u64); h = h.wrapping_mul(K); } self.hash = h; } #[inline(always)] fn write_u64(&mut self, i: u64) { self.write_u64_impl(i); } #[inline(always)] fn write_u32(&mut self, i: u32) { self.write_u64_impl(i as u64); } #[inline(always)] fn write_u16(&mut self, i: u16) { self.write_u64_impl(i as u64); } #[inline(always)] fn write_u8 (&mut self, i: u8 ) { self.write_u64_impl(i as u64); } #[inline(always)] fn write_usize(&mut self, i: usize) { self.write_u64_impl(i as u64); } #[inline(always)] fn write_i64(&mut self, i: i64) { self.write_u64_impl(i as u64); } #[inline(always)] fn write_i32(&mut self, i: i32) { self.write_u64_impl(i as u64); } #[inline(always)] fn write_i16(&mut self, i: i16) { self.write_u64_impl(i as u64); } #[inline(always)] fn write_i8 (&mut self, i: i8 ) { self.write_u64_impl(i as u64); } #[inline(always)] fn write_isize(&mut self, i: isize) { self.write_u64_impl(i as u64); } } pub type FxBuildHasher = BuildHasherDefault; pub type FxMap = std::collections::HashMap; pub type FxSet = std::collections::HashSet; } pub fn gcd(mut a: i64, mut b: i64)->i64{a=a.abs();b=b.abs();if a==0{return b;}else if b==0{return a;}let l1 = a.trailing_zeros();let l2 = b.trailing_zeros(); a >>= l1; b >>= l2;while a!=b{let x = (a^b).trailing_zeros();if a>x;}a << l1.min(l2)} pub fn gcd_i32(mut a: i32, mut b: i32)->i32{a=a.abs();b=b.abs();if a==0{return b;}else if b==0{return a;}let l1 = a.trailing_zeros();let l2 = b.trailing_zeros(); a >>= l1; b >>= l2;while a!=b{let x = (a^b).trailing_zeros();if a>x;}a << l1.min(l2)} pub fn factorial_i64(n: usize)->(Vec, Vec){ let mut res = vec![1; n+1];let mut inv = vec![1; n+1];for i in 0..n{ res[i+1] = (res[i]*(i+1)as i64)%MOD; } inv[n] = mod_inverse(res[n], MOD);for i in (0..n).rev(){ inv[i] = inv[i+1]*(i+1) as i64%MOD; }(res, inv) } pub fn floor(a:i64, b:i64)->i64{let res=(a%b+b)%b;(a-res)/b} pub fn modulo(a: i64, b: i64)->i64{(a%b+b)%b} pub fn extended_gcd(a:i64,b:i64)->(i64,i64,i64) {if b==0{(a,1,0)}else{let(g,x,y)=extended_gcd(b,a%b);(g,y,x-floor(a,b)*y)}} pub fn mod_inverse(a:i64,m:i64)->i64{let(_,x,_) =extended_gcd(a,m);(x%m+m)%m} pub fn comb(a: i64, b: i64, f: &Vec<(i64, i64)>)->i64{ if aVec<(i64, i64)>{ let mut f=vec![(1i64,1i64),(1, 1)];let mut z = 1i64; let mut inv = vec![0; x as usize+10];inv[1] = 1; for i in 2..x+1{z=(z*i)%MOD; let w=(MOD-inv[(MOD%i)as usize]*(MOD/i)%MOD)%MOD; inv[i as usize] = w; f.push((z, (f[i as usize-1].1*w)%MOD));}return f;} pub fn fast_mod_pow(mut x: i64,p: usize, m: i64)->i64{ x %= m; let mut res=1;let mut t=x;let mut z=p;while z > 0{ if z%2==1{res = (res*t)%m;}t = (t*t)%m;z /= 2; }res} pub trait SortD{ fn sort_d(&mut self); } impl SortD for Vec{ fn sort_d(&mut self) {self.sort_by(|u, v| v.cmp(&u));} } pub trait Mx{fn max(&self, rhs: Self)->Self;} impl Mx for f64{ fn max(&self, rhs: Self)->Self{if *self < rhs{ rhs } else { *self } }} pub trait Mi{ fn min(&self, rhs: Self)->Self; } impl Mi for f64{ fn min(&self, rhs: Self)->Self{ if *self > rhs{ rhs } else { *self } } } pub trait Chmax: PartialOrd + Copy {fn chmax(&mut self, rhs: Self) {if *self < rhs { *self = rhs; }}} impl Chmax for T {} pub trait Chmin: PartialOrd + Copy {fn chmin(&mut self, rhs: Self) {if *self > rhs { *self = rhs; }}} impl Chmin for T {} #[allow(unused)] use proconio::{*, marker::*}; #[allow(unused)] use fxhash::FxMap; #[allow(unused)] use ac_library::{*}; pub struct MintCombination{ fact: Vec, inv_fact: Vec, inv: Vec, } impl MintCombination{ pub fn new(n: usize)->Self { let mut fact = vec![MI::new(1); n+1]; let mut inv_fact = vec![MI::new(0); n+1]; let mut inv = vec![MI::new(1); n+1]; for i in 0..n{ fact[i+1] = fact[i]*(i+1); } inv_fact[n] = MI::new(1)/fact[n]; for i in (0..n).rev(){ inv_fact[i] = inv_fact[i+1]*(i+1); inv[i+1] = fact[i]*inv_fact[i+1]; } MintCombination { fact, inv_fact, inv } } #[inline] pub fn inv(&self, x: usize)->MI{ self.inv[x] } #[inline] pub fn f(&self, x: usize)->MI{ self.fact[x] } #[inline] pub fn fi(&self, x: usize)->MI{ self.inv_fact[x] } #[inline] pub fn p(&self, x: usize, y: usize)->MI{ if x < y{MI::new(0)} else {self.fact[x]*self.inv_fact[x-y]} } #[inline] pub fn c(&self, x: usize, y: usize)->MI{ if x < y{return MI::new(0);} self.fact[x]*self.inv_fact[y]*self.inv_fact[x-y] } } #[allow(dead_code)] const INF: i64 = 1<<60; #[allow(dead_code)] const I: i32 = 1<<30; #[allow(dead_code)] const MOD: i64 = 998244353; #[allow(dead_code)] const D: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)]; #[allow(dead_code)] pub fn c2d(c: u8)->(usize, usize){match c{b'U'=>(!0,0),b'D'=>(1,0),b'L'=>(0,!0),b'R'=>(0,1),_=>unreachable!()}} #[allow(dead_code)] pub fn c2d_i64(c: u8)->(i64, i64){match c{b'U'=>(-1,0),b'D'=>(1,0),b'L'=>(0,-1),b'R'=>(0,1),_=>unreachable!()}} #[allow(dead_code)] pub fn join2str(v: &[T])->String{v.iter().map(|x| x.to_string()).collect::>().join(" ")} #[allow(dead_code)] pub fn join2nospace(v: &[T])->String{v.iter().map(|x| x.to_string()).collect::>().join("")} #[allow(dead_code)] const D2: [(usize, usize); 8] = [(1, 0), (1, 1), (0, 1), (!0, 1), (!0, 0), (!0, !0), (0, !0), (1, !0)]; pub struct CSR{ n: usize, ac: Vec, edge: Vec, } impl CSR{ pub fn new(n: usize, es: &[(usize, usize)])->Self{ let mut ac = vec![0; n+1]; for &(u, _) in es{ ac[u+1] += 1; } for i in 0..n{ ac[i+1] += ac[i]; } let mut cnt = ac.clone(); let mut edge = vec![0; ac[n]]; for &(u, v) in es{ edge[cnt[u]] = v; cnt[u] += 1; } CSR { n, ac, edge } } pub fn undirected_new(n: usize, es: &[(usize, usize)])->Self{ let mut e = Vec::with_capacity(es.len()<<1); for &(u, v) in es{ e.push((u, v)); e.push((v, u)); } Self::new(n, &e) } pub fn len(&self)->usize{ self.n } pub fn adj(&self, idx: usize)->&[usize]{ &self.edge[self.ac[idx]..self.ac[idx+1]] } pub fn adj_mut(&mut self, idx: usize)->&mut [usize]{ &mut self.edge[self.ac[idx]..self.ac[idx+1]] } } impl Index for CSR{ type Output = [usize]; fn index(&self, index: usize) -> &Self::Output { &self.edge[self.ac[index]..self.ac[index+1]] } } impl IndexMut for CSR{ fn index_mut(&mut self, index: usize) -> &mut Self::Output { &mut self.edge[self.ac[index]..self.ac[index+1]] } } pub struct UnweightedGraph{ n: usize, edge: CSR, } impl UnweightedGraph{ pub fn new(n: usize, edge: &[(usize, usize)])->Self{ UnweightedGraph{n, edge: CSR::undirected_new(n, &edge)} } pub fn bfs(&self, p: usize)->Vec{ let mut dist = vec![!0; self.n]; dist[p] = 0; let mut stack = VecDeque::new(); stack.push_back(p); while let Some(p) = stack.pop_front(){ for &nex in &self.edge[p]{ if dist[nex]==!0{ dist[nex] = dist[p]+1; stack.push_back(nex); } } } dist } pub fn farthest_point(&self, p: usize)->(usize, usize){ let d = self.bfs(p); let (mut res, mut mx) = (p, 0); for i in 0..self.n{ if d[i]!=!0 && d[i] > mx{ mx = d[i]; res = i; } } (mx, res) } pub fn n(&self)->usize{self.n} pub fn build_path(&self, u: usize, v: usize)->Option>{ let dist = self.bfs(u); if dist[v]==!0{return None} let mut res = Vec::new(); res.push(v); let mut p = v; while p != u{ let mut nx = 0; for &nex in &self.edge[p]{ if dist[nex]!=!0 && dist[nex]+1==dist[p]{ nx = nex; break; } } p = nx; res.push(p); } res.reverse(); Some(res) } pub fn path(&self, u: usize, v: usize)->Vec{ let dist = self.bfs(u); let mut res = Vec::new(); res.push(v); let mut p = v; while p != u{ let mut nx = 0; for &nex in &self.edge[p]{ if dist[nex]!=!0 && dist[nex]+1==dist[p]{ nx = nex; break; } } p = nx; res.push(p); } res.reverse(); res } } impl Index for UnweightedGraph{ type Output = [usize]; fn index(&self, index: usize) -> &Self::Output { &self.edge[index] } } pub struct HLDVertex { parent: Vec, head: Vec, depth: Vec, int: Vec, out: Vec, seq: Vec, } impl HLDVertex { pub fn new(n: usize, r: usize, e: &[(usize, usize)])->Self{ let mut edge = UnweightedGraph::new(n, e); HLDVertex::size_dfs(r, !0, &mut edge); let mut int: Vec = vec![0; n]; let mut seq: Vec = Vec::with_capacity(n); let mut out: Vec = vec![0; n]; let mut parent: Vec = vec![!0; n]; let mut head: Vec = vec![0; n]; let mut depth: Vec = vec![0; n]; HLDVertex::euler_tour(r, !0, r, &edge, &mut parent, &mut depth, &mut head, &mut int, &mut out, &mut seq); HLDVertex { parent, head, depth, int, out, seq,} } #[inline] fn size_dfs(p: usize, pre: usize, edge: &mut UnweightedGraph)->usize{ let mut res = 1; let l = (&edge[p]).len(); let mut mx = 0; let mut rv = 0; for i in 0..l{ let nex = edge[p][i]; if nex==pre{continue;} let nn = HLDVertex::size_dfs(nex, p, edge); if mx < nn { mx = nn; rv = i; } res += nn; } if rv!=0{edge.edge[p].swap(0, rv)}; res } #[inline] fn euler_tour(p: usize, pre: usize, h: usize, edge: &UnweightedGraph, parent: &mut [u32], depth: &mut [u32], head: &mut [u32], int: &mut [u32], end: &mut [u32], seq: &mut Vec){ int[p] = seq.len()as u32; seq.push(p as u32); head[p] = h as u32; if edge[p].is_empty() || edge[p][0]==pre{ end[p] = seq.len()as u32; return; } let hc = edge[p][0]; depth[hc] = depth[p]+1; parent[hc]=p as u32; HLDVertex::euler_tour(hc, p, h, edge, parent, depth, head, int, end, seq); for &nex in &edge[p][1..]{ if nex==pre{continue;} depth[nex] = depth[p]+1; parent[nex]=p as u32; HLDVertex::euler_tour(nex, p, nex, edge, parent, depth, head, int, end, seq); } end[p] = seq.len() as u32; } #[inline] pub fn parent_up_k(&self, mut p: usize, mut k: usize)->usize{ if (self.depth[p]as usize) < k {return !0;} while self.int[p]as usize-self.int[self.head[p]as usize]as usize+1 <= k{ k -= self.int[p]as usize-self.int[self.head[p]as usize]as usize+1; p = self.parent[self.head[p]as usize]as usize; } self.seq[self.int[p]as usize-k]as usize } #[inline] pub fn parent_at_k(&self, p: usize, k: usize)->usize{ if (self.depth[p]as usize) < k{return !0;} self.parent_up_k(p, self.depth[p]as usize-k) } #[inline] pub fn lca(&self, mut u: usize, mut v: usize)->usize{ while self.head[u]!=self.head[v]{ if self.int[self.head[u]as usize]>self.int[self.head[v]as usize]{ swap(&mut u, &mut v); } v = self.parent[self.head[v]as usize]as usize; } if self.int[u]>self.int[v]{v} else {u} } #[inline] pub fn subtree(&self, p: usize)->(usize, usize){ (self.int[p]as usize, self.out[p]as usize) } #[inline] pub fn distance(&self, u: usize, v: usize)->usize{ let p = self.lca(u, v); (self.depth[u]+self.depth[v]-self.depth[p]*2)as usize } #[inline] pub fn jump_k(&self, u: usize, v: usize, k: usize)->usize{ let p = self.lca(u, v); let du = (self.depth[u]-self.depth[p])as usize; let dv = (self.depth[v]-self.depth[p])as usize; let d = du+dv; if d < k{return !0;} if k <= du { self.parent_up_k(u, k) } else { self.parent_up_k(v, d-k) } } pub fn all_path(&self, mut u: usize, mut v: usize)->Vec{ let mut res = vec![u]; let p = self.lca(u, v); while u!=p{ u = self.parent[u]as usize; res.push(u); } let mut rev = Vec::new(); while v!=p{ rev.push(v); v = self.parent[v]as usize; } rev.reverse(); res.extend(rev); res } // (left, right, rev: bool) #[inline] pub fn path(&self, mut u: usize, mut v: usize)->Vec<(usize, usize, bool)> { let mut res = Vec::new(); let mut rev = Vec::new(); while self.head[u]!=self.head[v]{ let hu = self.head[u]as usize; let hv = self.head[v]as usize; if self.depth[hu] >= self.depth[hv] { res.push((self.int[hu]as usize, self.int[u]as usize+1, true)); u=self.parent[hu]as usize; } else { rev.push((self.int[hv]as usize, self.int[v]as usize+1, false)); v=self.parent[hv]as usize; } } if self.depth[u]<=self.depth[v]{ rev.push((self.int[u]as usize, self.int[v]as usize+1, false)); } else { res.push((self.int[v]as usize, self.int[u]as usize+1, true)); } rev.reverse(); res.extend(rev); res } #[inline] pub fn get_index(&self, p: usize)->usize{ self.int[p]as usize } } pub trait CommutativeDualSegmentTreeMonoid{ type S: Clone; type F: Clone; fn id_s()->Self::S; fn id_f()->Self::F; fn map(f: &Self::F, x: &Self::S)->Self::S; fn composition(f: &Self::F, g: &Self::F)->Self::F; } pub struct CommutativeDualSegmentTree where M: CommutativeDualSegmentTreeMonoid{ n: usize, lazy: Vec, data: Vec, } impl CommutativeDualSegmentTree where M: CommutativeDualSegmentTreeMonoid{ pub fn new(n: usize)->Self{ let n = n.next_power_of_two(); CommutativeDualSegmentTree{ n, data: vec![M::id_s(); n], lazy: vec![M::id_f(); 2*n] } } pub fn from(mut data: Vec)->Self{ let n = data.len().next_power_of_two(); while data.len() < n{ data.push(M::id_s()); } CommutativeDualSegmentTree{ n, data, lazy: vec![M::id_f(); 2*n], } } pub fn set(&mut self, p: usize, x: M::S){ self.data[p] = x.clone(); } pub fn apply(&mut self, mut l: usize, mut r: usize, f: M::F){ l += self.n; r += self.n; while l < r{ if l&1==1{ self.lazy[l] = M::composition(&f, &self.lazy[l]); l += 1; } if r&1==1{ r -= 1; self.lazy[r] = M::composition(&f, &self.lazy[r]); } l >>= 1; r >>= 1; } } pub fn get(&self, mut p: usize)->M::S{ let mut res = self.data[p].clone(); p += self.n; while p > 0{ res = M::map(&self.lazy[p], &res); p >>= 1; } res } } struct M; impl CommutativeDualSegmentTreeMonoid for M{ type S = i64; type F = i64; fn id_s()->Self::S { 0 } fn id_f()->Self::F { 0 } fn map(&f: &Self::F, &x: &Self::S)->Self::S { f+x } fn composition(&f: &Self::F, &g: &Self::F)->Self::F { f+g } } #[allow(unused)] type MI = StaticModInt; const MULTI: bool = false; #[fastout] fn solve(){ input!{ n: usize, e: [(Usize1, Usize1); n-1], q: usize, query: [(Usize1, Usize1); q], } let hld = HLDVertex::new(n, 0, &e); let mut seg = CommutativeDualSegmentTree::::new(n); for &(u, v) in &query{ for (l, r, _) in hld.path(u, v){ seg.apply(l, r, 1); } } let mut ans = 0; for i in 0..n{ let x = seg.get(i); ans += x*(x+1)/2; } println!("{}", ans); } fn main() { if MULTI{ input!{ t: usize, } for _ in 0..t{ solve(); } } else { solve(); } }