#![allow(unused_imports,non_snake_case,dead_code)] use std::{cmp::Reverse as Rev,ops::Range,collections::*,iter::*,mem::swap}; use proconio::{marker::*,*}; #[fastout] fn main(){ input!{ n:usize, es:[(Usize1,Usize1);n-1], } let mut g=vec![vec![];n]; for &(u,v) in &es{ g[u].push(v); g[v].push(u); } cap!{ #![&g:Vec>] fn dist(p:usize,v:usize,d:&mut [usize]){ if p==!0{ d[v]=0; } else{ d[v]=d[p]+1; } for &nv in &g[v]{ if nv!=p{ dist!(v,nv,d); } } } } let mut a=vec![0;n]; dist!(!0,0,&mut a); let u=(0..n).max_by_key(|&i|a[i]).unwrap(); let mut ud=vec![0;n]; dist!(!0,u,&mut ud); let v=(0..n).max_by_key(|&i|ud[i]).unwrap(); let mut vd=vec![0;n]; dist!(!0,v,&mut vd); let lca=LCA::new(&g,0); let INF=1e8 as usize; let mut cur=([0;3],INF); for m in 0..n{ if m==u || m==v{ continue; } let mut a=[lca.get_dist(u,v),lca.get_dist(u,m),lca.get_dist(m,v)]; a.sort(); let es=lca.get_virtual_tree(&[u,v,m]); let mut tot=0; for &(u,v) in &es{ tot+=lca.get_dist(u,v); } if cur.0{}; (#![] $($fn:tt)*)=>{ cap!([],[],[],[],[$($fn)*],[],[]); }; (#![$($g:tt)*] $($fn:tt)*)=>{ cap!([$($g)*,],[],[],[],[$($fn)*],[],[]); }; ([$name:ident:$t:ty,$($rem:tt)*],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$($fn:tt)*],[],[])=>{ cap!([$($rem)*],[$name:$t,$($ga)*],[$name,$($gn)*],[$name,$($ge)*],[$($fn)*],[],[]); }; ([$($flag:tt)? $name:ident:$t:ty,$($rem:tt)*],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$($fn:tt)*],[],[])=>{ cap!([$($rem)*],[$name:$($flag)?$t,$($ga)*],[$name,$($gn)*],[$($flag)?$name,$($ge)*],[$($fn)*],[],[]); }; ([&mut $name:ident:$t:ty,$($rem:tt)*],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$($fn:tt)*],[],[])=>{ cap!([$($rem)*],[$name:&mut $t,$($ga)*],[$name,$($gn)*],[&mut $name,$($ge)*],[$($fn)*],[],[]); }; ([$(,)?],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$(#[$($att:tt)*])? fn $name:ident($($arg:tt)*) $body:block $($rem:tt)*],[$($info:tt)*],[$($fn:tt)*])=>{ cap!([],[$($ga)*],[$($gn)*],[$($ge)*],[$($rem)*],[(($(#[$($att)*])?),$name,($($arg)*),(),$body),$($info)*],[$name,$($fn)*]); }; ([$(,)?],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$(#[$($att:tt)*])? fn $name:ident($($arg:tt)*)->$ret:ty $body:block $($rem:tt)*],[$($info:tt)*],[$($fn:tt)*])=>{ cap!([],[$($ga)*],[$($gn)*],[$($ge)*],[$($rem)*],[(($(#[$($att)*])?),$name,($($arg)*),$ret,$body),$($info)*],[$name,$($fn)*]); }; ([$(,)?],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[],[$($info:tt)*],[$($fn:tt)*])=>{ cap!(@make_fn [$($ga)*],[$($gn)*],[$($ge)*],[$($info)*],[$($fn)*]); }; (@make_fn [$($ga:ident:$gt:ty,)*],[$($gn:tt)*],[$($ge:tt)*],[(($($att:tt)*),$name:ident,($($arg:tt)*),$ret:ty,$body:block),$($rem:tt)*],[$($fn:tt)*])=>{ $($att)* fn $name($($ga:$gt,)*$($arg)*)->$ret{ $(#[allow(unused_variables)] let $ga=$ga;)* cap!(@make_macros ($),[$($gn)*],[$($fn)*]); $body } cap!(@make_fn [$($ga:$gt,)*],[$($gn)*],[$($ge)*],[$($rem)*],[$($fn)*]); }; (@make_fn [$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[],[$($fn:tt)*])=>{ cap!(@make_global_macros ($),[$($ge)*],[$($fn)*]); }; (@make_macros ($dol:tt),[$($gn:ident,)*],[$name:ident,$($rem:tt)*])=>{ #[allow(unused_macros)] macro_rules! $name{ ($dol($dol arg:expr),*)=>{$name($($gn,)* $dol($dol arg),*)} } cap!(@make_macros ($),[$($gn,)*],[$($rem)*]); }; (@make_macros ($dol:tt),[$($gn:ident,)*],[])=>{}; (@make_global_macros ($dol:tt),[$($ge:expr,)*],[$name:ident,$($rem:tt)*])=>{ #[allow(unused_macros)] macro_rules! $name{ ($dol($dol arg:expr),*)=>{$name($($ge,)* $dol($dol arg),*)} } cap!(@make_global_macros ($),[$($ge,)*],[$($rem)*]); }; (@make_global_macros ($dol:tt),[$($ge:expr,)*],[])=>{}; } type ModInt998244353=ModInt<998244353>; type ModInt1000000007=ModInt<1000000007>; #[derive(Clone,Copy,PartialEq,Eq,Default,Hash)] struct ModInt(u32); impl ModIntBase for ModInt{ fn modulus()->u32{ MOD } fn val(self)->u32{ self.0 } fn new(v:impl RemU32)->Self{ Self(v.rem_u32(MOD)) } fn inv(self)->Self{ assert!(self.0!=0); let (mut a,mut b)=(self.0 as i64,MOD as i64); let (mut u,mut v)=(1,0); while b!=0{ let t=a/b; (a,b)=(b,a-t*b); (u,v)=(v,u-t*v); } assert!(a==1); if u<0{ u+=MOD as i64; } Self(u as u32) } fn pow(self,mut k:u64)->Self{ let mut pow2=self; let mut ret=Self(1); while k>0{ if k&1==1{ ret*=pow2; } pow2*=pow2; k>>=1; } ret } } impl std::fmt::Display for ModInt{ fn fmt(&self,f:&mut std::fmt::Formatter)->std::fmt::Result{ write!(f,"{}",self.0) } } impl std::fmt::Debug for ModInt{ fn fmt(&self,f:&mut std::fmt::Formatter)->std::fmt::Result{ write!(f,"{}",self.0) } } impl std::ops::Add for ModInt{ type Output=Self; fn add(self,a:Self)->Self{ let mut new=self.0+a.0; if MOD<=new{ new-=MOD; } Self(new) } } impl std::ops::Sub for ModInt{ type Output=Self; fn sub(self,a:Self)->Self{ let mut new=self.0-a.0; if 0>new as i32{ new+=MOD; } Self(new) } } impl std::ops::Mul for ModInt{ type Output=Self; fn mul(self,a:Self)->Self{ Self((self.0 as u64*a.0 as u64%MOD as u64) as u32) } } impl std::ops::Div for ModInt{ type Output=Self; fn div(self,a:Self)->Self{ self*a.inv() } } impl std::ops::Neg for ModInt{ type Output=Self; fn neg(self)->Self{ if self.0==0{ return self; } Self(MOD-self.0) } } impl std::str::FromStr for ModInt{ type Err=::Err; fn from_str(s:&str)->Result{ let x=s.parse::()?; Ok(Self::new(x)) } } macro_rules! impl_modint_ops{ ($trait:ident,$func:ident,$assign_trait:ident,$assign_func:ident,$op:tt)=>{ impl std::ops::$assign_trait for ModInt{ fn $assign_func(&mut self,a:Self){ *self=*self $op a } } impl std::ops::$trait for ModInt{ type Output=Self; fn $func(self,a:T)->Self{ self $op Self::new(a) } } impl std::ops::$assign_trait for ModInt{ fn $assign_func(&mut self,a:T){ *self=*self $op Self::new(a) } } } } impl_modint_ops!(Add,add,AddAssign,add_assign,+); impl_modint_ops!(Sub,sub,SubAssign,sub_assign,-); impl_modint_ops!(Mul,mul,MulAssign,mul_assign,*); impl_modint_ops!(Div,div,DivAssign,div_assign,/); impl std::iter::Sum for ModInt{ fn sum>(iter:I)->Self{ iter.fold(Self(0),|sum,x|sum+x) } } impl std::iter::Product for ModInt{ fn product>(iter:I)->Self{ iter.fold(Self(1),|prod,x|prod*x) } } trait RemU32{ fn rem_u32(self,m:u32)->u32; } macro_rules! impl_rem_u32{ ($($ty:tt),*)=>{ $( impl RemU32 for $ty{ fn rem_u32(self,m:u32)->u32{ (self as i64).rem_euclid(m as i64) as _ } } )* } } impl_rem_u32!(i32,i64); macro_rules! impl_rem_u32{ ($($ty:tt),*)=>{ $( impl RemU32 for $ty{ fn rem_u32(self,m:u32)->u32{ (self%(m as $ty)) as _ } } )* } } impl_rem_u32!(u32,u64,usize); trait ModIntBase:Default+std::str::FromStr+Copy+Eq+std::hash::Hash+std::fmt::Display+std::fmt::Debug +std::ops::Neg+std::ops::Add+std::ops::Sub +std::ops::Mul+std::ops::Div +std::ops::AddAssign+std::ops::SubAssign+std::ops::MulAssign+std::ops::DivAssign { fn modulus()->u32; fn val(self)->u32; fn new(v:impl RemU32)->Self; fn inv(self)->Self; fn pow(self,k:u64)->Self; } #[derive(Clone)] struct LCA{ range:Vec<(usize,usize)>, sparse_table:Vec>, rank:Vec, } impl LCA{ fn new(tree:&Vec>,root:usize)->LCA{ let n=tree.len(); let mut tour=vec![]; let mut range=vec![(!0,!0);n]; let mut rank=vec![0;n]; fn rec(tree:&Vec>,p:usize,v:usize,tour:&mut Vec,range:&mut [(usize,usize)],rank:&mut [usize]){ range[v].0=tour.len(); tour.push(v); for &nv in &tree[v]{ if nv!=p{ rank[nv]=rank[v]+1; rec(tree,v,nv,tour,range,rank); } range[v].1=tour.len(); tour.push(v); } } rec(tree,!0,root,&mut tour,&mut range,&mut rank); let min=|u:usize,v:usize|->usize{ if rank[u]usize{ let rank=&self.rank; if rank[u]>rank[v]{ (u,v)=(v,u); } let ru=self.range[u]; let rv=self.range[v]; if ru.0<=rv.0 && rv.1<=ru.1{ return u; } let mut l=ru.0; let mut r=rv.0; if l>r{ (l,r)=(r,l); } let step=(usize::BITS-1-(r-l).leading_zeros()) as usize; let a=self.sparse_table[step][l]; let b=self.sparse_table[step][r-(1<usize{ let lca=self.get_lca(u,v); self.rank[u]+self.rank[v]-self.rank[lca]*2 } fn get_virtual_tree(&self,vs:&[usize])->Vec<(usize,usize)>{ if vs.is_empty(){ return vec![]; } let rank=&self.rank; let mut vs=vs.to_vec(); vs.sort_unstable_by_key(|&v|self.range[v].1); let mut es=vec![]; let mut stack=vec![vs[0]]; for &v in &vs[1..]{ let lca=self.get_lca(*stack.last().unwrap(),v); let mut prev=!0; while let Some(&v)=stack.last(){ if rank[lca]>rank[v]{ break; } let nv=stack.pop().unwrap(); if prev!=!0{ es.push((nv,prev)); } prev=nv; } if prev!=!0 && lca!=prev{ es.push((lca,prev)); } stack.push(lca); if lca!=v{ stack.push(v); } } for w in stack.windows(2){ es.push((w[1],w[0])); } es } }