【LOJ #3070】「2019 集训队互测 Day 1」最短路径(分治..._CSDN博客

来自 : CSDN技术社区 发布时间：2021-03-25

while(!isdigit(ch))f^ ch - ,ch gc(); while(isdigit(ch))res (res (res 2) 1) (ch^48),ch gc(); return f?res:-res;inline ll readll(){ char ch gc(); ll res 0;bool f 1; while(!isdigit(ch))f^ ch - ,ch gc(); while(isdigit(ch))res (res (res 2) 1) (ch^48),ch gc(); return f?res:-res;inline int readstring(char *s){ int top 0;char ch gc(); while(isspace(ch))ch gc(); while(!isspace(ch) ch! EOF)s[ top] ch,ch gc(); s[top 1] \\0 ;return top;template typename tp inline void chemx(tp a,tp b){a max(a,b);}template typename tp inline void chemn(tp a,tp b){a min(a,b);}cs int mod 998244353;inline int add(int a,int b){return (a b) mod?(a b-mod):(a b);}inline int dec(int a,int b){return (a b)?(a-b mod):(a-b);}inline int mul(int a,int b){static ll r;r (ll)a*b;return (r mod)?(r%mod):r;}inline void Add(int a,int b){a (a b) mod?(a b-mod):(a b);}inline void Dec(int a,int b){a (a b)?(a-b mod):(a-b);}inline void Mul(int a,int b){static ll r;r (ll)a*b;a (r mod)?(r%mod):r;}inline int ksm(int a,ll b,int res 1){for(;b;b 1,Mul(a,a))(b 1) (Mul(res,a),1);return res;}inline int Inv(int x){return ksm(x,mod-2);}inline int fix(ll x){x% mod;return (x 0)?x mod:x;}cs int N 100005;int n,K;typedef vector int poly;namespace Poly{ cs int C 18,M (1 C)|5; int rev[M],*w[C 1]; inline void init_w(){ for(int i 1;i C;i )w[i] new int[(1 (i-1))|1]; int wn ksm(3,(mod-1)/(1 C));w[C][0] 1; for(int i 1,l 1 (C-1);i l;i )w[C][i] mul(w[C][i-1],wn); for(int i C-1;i;i--) for(int j 0,l 1 (i-1);j l;j ) w[i][j] w[i 1][j 1]; inline void init_rev(int lim){ for(int i 0;i lim;i )rev[i] (rev[i 1] 1)|((i 1)*(lim 1)); inline void ntt(int *f,int lim,int kd){ for(int i 0;i lim;i )if(i rev[i])swap(f[i],f[rev[i]]); for(int mid 1,l 1,a0,a1;mid lim;mid 1,l ) for(int i 0;i lim;i mid 1) for(int j 0;j mid;j ) a0 f[i j],a1 mul(f[i j mid],w[l][j]),f[i j] add(a0,a1),f[i j mid] dec(a0,a1); if(kd -1){ reverse(f 1,f lim); for(int i 0,iv Inv(lim);i lim;i )Mul(f[i],iv); inline void operator (poly a,cs poly b){ if(a.size() b.size())a.resize(b.size()); for(int i 0;i b.size();i )Add(a[i],b[i]); inline poly operator *(poly a,poly b){ if(!a.size()||!b.size())return poly(0); int deg a.size() b.size()-1; if(a.size() 16||b.size() 16){ poly c(deg,0); for(int i 0;i a.size();i ) for(int j 0;j b.size();j ) Add(c[i j],mul(a[i],b[j])); return c; int lim 1; while(lim deg)lim 1; init_rev(lim); a.resize(lim),ntt( a[0],lim,1); b.resize(lim),ntt( b[0],lim,1); for(int i 0;i lim;i )Mul(a[i],b[i]); ntt( a[0],lim,-1),a.resize(deg); return a;using namespace Poly;vector int e[N],p[N];int pre[N],dep[N],is_loop[N],pt[N],ans[N],num;bool find_loop(int u,int fa){ for(cs int v:e[u])if(v! fa){ if(!dep[v]){ dep[v] dep[u] 1,pre[v] u; if(find_loop(v,u))return true; else if(dep[v] dep[u]){ int p u; while(p! v){ pt[ num] p; is_loop[p] 1; p pre[p]; }pt[ num] v; is_loop[v] 1; return true; return false;int mx,rt,maxn,vis[N],siz[N];namespace tre{ void getrt(int u,int fa){ siz[u] 1;int son 0; for(int v:e[u])if(v! fa !vis[v]){ getrt(v,u),siz[u] siz[v]; chemx(son,siz[v]); chemx(son,maxn-siz[u]); if(son mx)mx son,rt u; void getdep(int u,int fa,int dep,poly anc){ if(dep anc.size())anc.resize(dep 1); anc[dep] ;siz[u] 1; for(int v:e[u])if(v! fa !vis[v]){ getdep(v,u,dep 1,anc),siz[u] siz[v]; void solve(int u){ vis[u] 1; poly f; for(int v:e[u])if(!vis[v]){ poly g; getdep(v,u,1,g); f g; g g*g; for(int i 0;i g.size();i )Dec(ans[i],g[i]); for(int i 0;i f.size();i )Add(ans[i],mul(2,f[i])); f f*f; for(int i 0;i f.size();i )Add(ans[i],f[i]); for(int v:e[u])if(!vis[v]){ maxn mx siz[v],rt 0; getrt(v,u),solve(rt);inline void calc(int l1,int r1,int l2,int r2,int dis){ int mx1 0,mx2 0; for(int i l1;i r1;i )chemx(mx1,r1-i (int)p[i].size()); for(int i l2;i r2;i )chemx(mx2,i-l2 (int)p[i].size()); poly f(mx1),g(mx2); for(int i l1;i r1;i ){ for(int j 0;j (int)p[i].size();j ) Add(f[r1-i j],p[i][j]); for(int i l2;i r2;i ){ for(int j 0;j (int)p[i].size();j ) Add(g[i-l2 j],p[i][j]); f f*g; for(int i 0;i f.size();i )Add(ans[i dis],f[i]);void solve1(int l,int r){ if(l r)return; int mid (l r) 1; solve1(l,mid);solve1(mid 1,r); calc(l,mid,mid 1,r,1);void solve2(int l1,int r1,int l2,int r2,int dis){ if(l1 r1){ calc(l1,r1,l2,r2,dis); return; int m1 (l1 r1) 1,m2 (l2 r2) 1; calc(m1 1,r1,l2,m2,dis); solve2(l1,m1,l2,m2,dis r1-m1); solve2(m1 1,r1,m2 1,r2,dis m1-l1 1);int main(){ #ifdef Stargazer freopen( lx.in , r ,stdin); #endif Poly::init_w(); n read(),K read()%(mod-1); bool ist 0; for(int i 1;i n;i ){ int u read(),v read(); if(u! v) e[u].pb(v),e[v].pb(u); else ist 1; if(!ist)find_loop(1,0); else pt[num 1] 1; for(int i 1;i num;i )vis[pt[i]] 1; for(int i 1;i num;i ){ int u pt[i];vis[u] 0; tre::getdep(u,0,0,p[i]); maxn mx siz[u]; tre::getrt(u,rt 0); tre::solve(rt); for(int i 1,iv Inv(2);i n;i )Mul(ans[i],iv); if(num 1){ solve1(1,num/2),solve1(num/2 1,num); if(num 1){ solve2(1,num/2,num/2 1,num-1,1); solve2(num/2 2,num,1,num/2,1); else{ solve2(1,num/2,num/2 1,num,1); solve2(num/2 2,num,1,num/2-1,1); int res 0; for(int i 1;i n;i )Add(res,mul(ksm(i,K),ans[i])); Mul(res,Inv(fix((ll)n*(n-1)/2))); cout res \\n ;return 0;