pub use __cargo_equip::prelude::*; use acl_lazysegtree::{LazySegtree, MapMonoid}; use acl_segtree::Monoid; use hld::Hld; use proconio::{input, marker::Usize1}; #[derive(Clone)] struct Data { value: usize, size: usize, } struct Sum; impl Monoid for Sum { /// /// モノイドの型 /// type S = Data; /// /// 単位元 /// fn identity() -> Self::S { Data { value: 0, size: 0 } } /// /// 二項演算 /// fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { Data { value: a.value + b.value, size: a.size + b.size, } } } struct SumAdd; impl MapMonoid for SumAdd { type M = Sum; /// 写像の型 type F = usize; /// /// 恒等写像 /// 全ての`a`に対して`mapping(id, a) = a`となるもの /// fn identity_map() -> Self::F { 0 } /// /// f(x) を返す関数 /// /// dataの値`x`に対して作用させる関数 /// fn mapping(f: &Self::F, x: &::S) -> ::S { Data { value: x.value + x.size * f, size: x.size, } } /// /// f∘g を返す関数 /// /// `g` がこれまでの操作、`f` が後に追加する操作で、 ///「その2つの操作を順に行うようなひとまとめの操作(合成写像)」を返す /// fn composition(&f: &Self::F, &g: &Self::F) -> Self::F { f + g } } fn main() { input! { n: usize, u_v: [(Usize1, Usize1); n - 1], q: usize, a_b: [(Usize1, Usize1); q], } let mut list = vec![Vec::new(); n]; for &(u, v) in &u_v { list[u].push(v); list[v].push(u); } let hld = Hld::new(0, &list); // println!("{:?}", hld); let mut tree = LazySegtree::::from(vec![Data { value: 0, size: 1 }; n]); let mut result = 0; for &(a, b) in &a_b { // println!("---- {} {}", a, b); for (u, v) in hld.iter_v(a, b) { // println!("{}({}) {}({})", hld.ord()[u], u, hld.ord()[v], v); tree.apply_range(u, v + 1, 1); result += tree.prod(u, v + 1).value; } // for i in 0..n { // println!("i {} w {}", i, tree.get(i).value); // } } println!("{}", result); } // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `ac-library-rs-parted-internal-bit 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__ac_library_rs_parted_internal_bit_0_1_0` /// - `ac-library-rs-parted-internal-type-traits 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__ac_library_rs_parted_internal_type_traits_0_1_0` /// - `ac-library-rs-parted-lazysegtree 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::acl_lazysegtree` /// - `ac-library-rs-parted-segtree 0.1.0 (git+https://github.com/qryxip/ac-library-rs-parted#77261929d6551609cf352f4f9e05b34bafd5a8f7)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::acl_segtree` /// - `hld 0.1.0 (git+https://github.com/ngtkana/ac-adapter-rs.git?rev=624ecef1fb67c2e0a42752fb9cd5339f99e5c318#624ecef1fb67c2e0a42752fb9cd5339f99e5c318)` licensed under **missing** as `crate::__cargo_equip::crates::hld` #[cfg_attr(any(), rustfmt::skip)] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod __ac_library_rs_parted_internal_bit_0_1_0 {pub use self::internal_bit::*;mod internal_bit{#[allow(dead_code)]pub fn ceil_pow2(n:u32)->u32{32-n.saturating_sub(1).leading_zeros()}}} pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {pub use self::internal_type_traits::*;mod internal_type_traits{use std::{fmt,iter::{Product,Sum},ops::{Add,AddAssign,BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Div,DivAssign,Mul,MulAssign,Not,Rem,RemAssign,Shl,ShlAssign,Shr,ShrAssign,Sub,SubAssign,},};pub trait Integral:'static+Send+Sync+Copy+Ord+Not+Add+Sub+Mul+Div+Rem+AddAssign+SubAssign+MulAssign+DivAssign+RemAssign+Sum+Product+BitOr+BitAnd+BitXor+BitOrAssign+BitAndAssign+BitXorAssign+Shl+Shr+ShlAssign+ShrAssign+fmt::Display+fmt::Debug+fmt::Binary+fmt::Octal+Zero+One+BoundedBelow+BoundedAbove{}pub trait Zero{fn zero()->Self;}pub trait One{fn one()->Self;}pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::min_value()}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::max_value()}}impl Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}} pub mod acl_lazysegtree {use crate::__cargo_equip::preludes::acl_lazysegtree::*;use crate::__cargo_equip::crates::__ac_library_rs_parted_internal_bit_0_1_0 as internal_bit;use crate::__cargo_equip::crates::acl_segtree as segtree;pub use self::lazysegtree::*;mod lazysegtree{use crate::__cargo_equip::preludes::acl_lazysegtree::*;use super::internal_bit::ceil_pow2;use super::segtree::Monoid;pub trait MapMonoid{type M:Monoid;type F:Clone;fn identity_element()->::S{Self::M::identity()}fn binary_operation(a:&::S,b:&::S,)->::S{Self::M::binary_operation(a,b)}fn identity_map()->Self::F;fn mapping(f:&Self::F,x:&::S)->::S;fn composition(f:&Self::F,g:&Self::F)->Self::F;}implDefault for LazySegtree{fn default()->Self{Self::new(0)}}implLazySegtree{pub fn new(n:usize)->Self{vec![F::identity_element();n].into()}}implFrom::S>>for LazySegtree{fn from(v:Vec<::S>)->Self{let n=v.len();let log=ceil_pow2(n as u32)as usize;let size=1<LazySegtree{pub fn set(&mut self,mut p:usize,x:::S){assert!(p>i);}self.d[p]=x;for i in 1..=self.log{self.update(p>>i);}}pub fn get(&mut self,mut p:usize)->::S{assert!(p>i);}self.d[p].clone()}pub fn prod(&mut self,mut l:usize,mut r:usize)->::S{assert!(l<=r&&r<=self.n);if l==r{return F::identity_element();}l+=self.size;r+=self.size;for i in(1..=self.log).rev(){if((l>>i)<>i);}if((r>>i)<>i);}}let mut sml=F::identity_element();let mut smr=F::identity_element();while l>=1;r>>=1;}F::binary_operation(&sml,&smr)}pub fn all_prod(&self)->::S{self.d[1].clone()}pub fn apply(&mut self,mut p:usize,f:F::F){assert!(p>i);}self.d[p]=F::mapping(&f,&self.d[p]);for i in 1..=self.log{self.update(p>>i);}}pub fn apply_range(&mut self,mut l:usize,mut r:usize,f:F::F){assert!(l<=r&&r<=self.n);if l==r{return;}l+=self.size;r+=self.size;for i in(1..=self.log).rev(){if((l>>i)<>i);}if((r>>i)<>i);}}{let l2=l;let r2=r;while l>=1;r>>=1;}l=l2;r=r2;}for i in 1..=self.log{if((l>>i)<>i);}if((r>>i)<>i);}}}pub fn max_right(&mut self,mut l:usize,g:G)->usize where G:Fn(::S)->bool,{assert!(l<=self.n);assert!(g(F::identity_element()));if l==self.n{return self.n;}l+=self.size;for i in(1..=self.log).rev(){self.push(l>>i);}let mut sm=F::identity_element();while{while l%2==0{l>>=1;}if!g(F::binary_operation(&sm,&self.d[l])){while l(&mut self,mut r:usize,g:G)->usize where G:Fn(::S)->bool,{assert!(r<=self.n);assert!(g(F::identity_element()));if r==0{return 0;}r+=self.size;for i in(1..=self.log).rev(){self.push((r-1)>>i);}let mut sm=F::identity_element();while{r-=1;while r>1&&r%2!=0{r>>=1;}if!g(F::binary_operation(&self.d[r],&sm)){while rwhere F:MapMonoid,{n:usize,size:usize,log:usize,d:Vec<::S>,lz:Vec,}implLazySegtreewhere F:MapMonoid,{fn update(&mut self,k:usize){self.d[k]=F::binary_operation(&self.d[2*k],&self.d[2*k+1]);}fn all_apply(&mut self,k:usize,f:F::F){self.d[k]=F::mapping(&f,&self.d[k]);if kDebug for LazySegtreewhere F:MapMonoid,F::F:Debug,::S:Debug,{fn fmt(&self,f:&mut Formatter<'_>)->Result<(),Error>{for i in 0..self.log{for j in 0..1<Self::S;fn binary_operation(a:&Self::S,b:&Self::S)->Self::S;}pub struct Max(Infallible,PhantomDataS>);implMonoid for Maxwhere S:Copy+Ord+BoundedBelow,{type S=S;fn identity()->Self::S{S::min_value()}fn binary_operation(a:&Self::S,b:&Self::S)->Self::S{max(*a,*b)}}pub struct Min(Infallible,PhantomDataS>);implMonoid for Minwhere S:Copy+Ord+BoundedAbove,{type S=S;fn identity()->Self::S{S::max_value()}fn binary_operation(a:&Self::S,b:&Self::S)->Self::S{min(*a,*b)}}pub struct Additive(Infallible,PhantomDataS>);implMonoid for Additivewhere S:Copy+Add+Zero,{type S=S;fn identity()->Self::S{S::zero()}fn binary_operation(a:&Self::S,b:&Self::S)->Self::S{*a+*b}}pub struct Multiplicative(Infallible,PhantomDataS>);implMonoid for Multiplicativewhere S:Copy+Mul+One,{type S=S;fn identity()->Self::S{S::one()}fn binary_operation(a:&Self::S,b:&Self::S)->Self::S{*a**b}}implDefault for Segtree{fn default()->Self{Segtree::new(0)}}implSegtree{pub fn new(n:usize)->Segtree{vec![M::identity();n].into()}}implFrom>for Segtree{fn from(v:Vec)->Self{let n=v.len();let log=ceil_pow2(n as u32)as usize;let size=1<Segtree{pub fn set(&mut self,mut p:usize,x:M::S){assert!(p>i);}}pub fn get(&self,p:usize)->M::S{assert!(pM::S{assert!(l<=r&&r<=self.n);let mut sml=M::identity();let mut smr=M::identity();l+=self.size;r+=self.size;while l>=1;r>>=1;}M::binary_operation(&sml,&smr)}pub fn all_prod(&self)->M::S{self.d[1].clone()}pub fn max_right(&self,mut l:usize,f:F)->usize where F:Fn(&M::S)->bool,{assert!(l<=self.n);assert!(f(&M::identity()));if l==self.n{return self.n;}l+=self.size;let mut sm=M::identity();while{while l%2==0{l>>=1;}if!f(&M::binary_operation(&sm,&self.d[l])){while l(&self,mut r:usize,f:F)->usize where F:Fn(&M::S)->bool,{assert!(r<=self.n);assert!(f(&M::identity()));if r==0{return 0;}r+=self.size;let mut sm=M::identity();while{r-=1;while r>1&&r%2==1{r>>=1;}if!f(&M::binary_operation(&self.d[r],&sm)){while rwhere M:Monoid,{n:usize,size:usize,log:usize,d:Vec,}}} pub mod hld {use std::mem::swap;use std::usize::MAX;#[derive(Clone,Debug,Default,Hash,PartialEq,Eq)]pub struct Hld{child:Vec>,size:Vec,time:Vec,ord:Vec,parent:Vec,head:Vec,}impl Hld{pub fn new(root:usize,g:&[Vec])->Self{let(child,[size,time,ord,parent,head])=hld(root,g);Self{child,size,time,ord,parent,head,}}pub fn child(&self)->&[Vec]{&self.child}pub fn size(&self)->&[usize]{&self.size}pub fn time(&self)->&[usize]{&self.time}pub fn ord(&self)->&[usize]{&self.ord}pub fn parent(&self)->&[usize]{&self.parent}pub fn head(&self)->&[usize]{&self.head}pub fn is_adjacent(&self,u:usize,v:usize)->bool{assert!(uusize{assert!(xusize{self.iter_e(u,v).map(|(l,r)|r-l+1).sum::()}pub fn lca(&self,u:usize,v:usize)->usize{let(u,v)=self.iter_v(u,v).last().unwrap();self.ord[u.min(v)]}pub fn is_ancestor_of(&self,p:usize,u:usize)->bool{self.lca(p,u)==p}pub fn between(&self,a:usize,b:usize,c:usize)->bool{let mid=self.time[b];self.iter_v(a,c).any(|(left,right)|(left..=right).contains(&mid))}pub fn iter_v(&self,u:usize,v:usize)->IterV<'_>{IterV{hld:self,u,v,finish:false,}}pub fn iter_e(&self,u:usize,v:usize)->IterE<'_>{IterE{hld:self,u,v,finish:false,}}}#[derive(Clone,Debug,Hash,PartialEq,Eq)]pub struct IterV<'a>{hld:&'a Hld,u:usize,v:usize,finish:bool,}impl Iterator for IterV<'_>{type Item=(usize,usize);fn next(&mut self)->Option{if self.finish{return None;}let Self{hld,u,v,..}=self;if hld.time[*u]>hld.time[*v]{swap(u,v);}Some(if hld.head[*u]==hld.head[*v]{self.finish=true;(hld.time[*u],hld.time[*v])}else{let h=hld.head[*v];let ans=(hld.time[h],hld.time[*v]);assert_ne!(hld.parent[h],h,"入力のグラフが非連結です。");*v=hld.parent[h];ans})}}#[derive(Clone,Debug,Hash,PartialEq,Eq)]pub struct IterE<'a>{hld:&'a Hld,u:usize,v:usize,finish:bool,}impl Iterator for IterE<'_>{type Item=(usize,usize);fn next(&mut self)->Option{if self.finish{return None;}let Self{hld,u,v,..}=self;if hld.time[*u]>hld.time[*v]{swap(u,v);}if hld.head[*u]==hld.head[*v]{self.finish=true;if*u==*v{None}else{Some((hld.time[*u]+1,hld.time[*v]))}}else{let h=hld.head[*v];let ans=(hld.time[h],hld.time[*v]);assert_ne!(hld.parent[h],h,"入力のグラフが非連結です。");*v=hld.parent[h];Some(ans)}}}fn hld(root:usize,g:&[Vec])->(Vec>,[Vec;5]){let n=g.len();let mut size=vec![1;n];let mut child=vec![Vec::::new();n];dfs(root,root,g,&mut size,&mut child);let mut ord=Vec::new();let mut time=vec![MAX;n];let mut parent=vec![MAX;n];let mut head=vec![MAX;n];parent[root]=root;head[root]=root;efs(root,&child,&mut time,&mut ord,&mut parent,&mut head);assert!(parent.iter().all(|&x|x!=MAX),"入力が非連結です。");(child,[size,time,ord,parent,head])}fn dfs(x:usize,p:usize,g:&[Vec],size:&mut[usize],child:&mut[Vec]){let mut gx=g[x].iter().copied().filter(|&y|y!=p).collect::>();if!gx.is_empty(){for&y in&gx{dfs(y,x,g,size,child);size[x]+=size[y];}let max_position=(0..gx.len()).max_by_key(|&i|size[gx[i]]).unwrap();gx.swap(0,max_position);}child[x]=gx;}fn efs(x:usize,g:&[Vec],time:&mut[usize],ord:&mut Vec,parent:&mut[usize],head:&mut[usize],){time[x]=ord.len();ord.push(x);if!g[x].is_empty(){let h=g[x][0];head[h]=head[x];parent[h]=x;efs(h,g,time,ord,parent,head);for&y in&g[x][1..]{head[y]=y;parent[y]=x;efs(y,g,time,ord,parent,head);}}}} } pub(crate) mod macros { pub mod __ac_library_rs_parted_internal_bit_0_1_0 {} pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {} pub mod acl_lazysegtree {} pub mod acl_segtree {} pub mod hld {} } pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;} mod preludes { pub mod __ac_library_rs_parted_internal_bit_0_1_0 {} pub mod __ac_library_rs_parted_internal_type_traits_0_1_0 {} pub mod acl_lazysegtree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__ac_library_rs_parted_internal_bit_0_1_0 as __acl_internal_bit,acl_segtree as __acl_segtree};} pub mod acl_segtree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__ac_library_rs_parted_internal_bit_0_1_0 as __acl_internal_bit,__ac_library_rs_parted_internal_type_traits_0_1_0 as __acl_internal_type_traits};} pub mod hld {} } }