WC2019 T1 数树

WC2019 T1 数树

传送门（https://loj.ac/problem/2983）

Question 0

对于给定的两棵树，设记两颗树 (A,B) 的重边数量为 (R(A,B))，那么

[Ans=y^{n-R(A,B)} ]

Question 1

给定其中一棵树，求第二棵树的所有情况下答案的总和

不妨令 (y=y^{-1}) ,最终答案就是 (y^{-n}y^{R(A,B)})。

在给定 (A) 的情况下，只需要统计 (sumlimits_B y^{R(A,B)}) 即可

注意到(y^k=[(y-1)+1]^k=sumlimits_{i=0}^k (y-1)^i inom{k}{i})

及对于确定的 (A,B)，枚举一个边集 (S) ，若 (S) 中每一条边均为 (A,B) 重边，则其贡献为 ((y-1)^{|S|}) 否则为 (0)

特别的，我们把 (y-1=0​) 特判掉，因为不存在逆元。

考虑枚举每一个 (A​) 的边集，假设一共 (n-m​) 条边把 (n​) 个点划分成了 (m​) 个联通块。

设第 (i​) 个联通块有 (a_i​) 个点那么它的贡献为 ((y-1)^{n-m} imes​) 包含这(n-m​) 条边的树的个数。

把每一个联通块当作一个点，考虑枚举每个联通块的度数 (d_i) 通过 (prufer) 序列我们知道答案为

[Ans=(y-1)^{n-m}sumlimits_{(sum a_i)=n,(sum d_i)=2(m-2)} m^{m-2}(prod_{i=1}^m a_i^{d_i})(prod_{i=1}^m inom{sum_{j=1}^i(d_j-1)}{d_i-1}) \ =(y-1)^{n-m}sumlimits_{(sum a_i)=n,(sum d_i)=2m-2} m^{m-2}(prod_{i=1}^m a_i^{d_i})frac{(m-2)!}{prod_{i=1}^m(d_i-1)!}\ =(y-1)^{n-m}sumlimits_{(sum a_i)=n,(sum d_i)=m-2} (prod_{i=1}^m a_i)(m-2)!m^{m-2}prod_{i=1}^m frac{a_i^{d_i}}{d_i!}\ =(y-1)^{n-m}sumlimits_{(sum a_i)=n} (prod_{i=1}^m a_i)n^{m-2}\ =(y-1)^n n^{-2}sumlimits_{(sum a_i)=n} (prod_{i=1}^m a_i)n^m (y-1)^{-m}\ =(y-1)^n n^{-2}sumlimits_{(sum a_i)=n} (prod_{i=1}^m a_i(y-1)^{-1}n)\ ]

注意 ((prod_{i=1}^m a_i)) 表示每个联通块中选一个关键点的方案数量，这样就可以设 (F_{x,0/1}) 表示 (x) 号点所在联通块是否选出关键点的贡献和，树形 (DP) ，每次考虑父子的边是否被选中即可。

Question 2

和 (Question 1​) 的做法类似，先特判 $y-1=​$0 考虑枚举一个边集构成了 $ m ​$ 个的联通块的答案

[Ans=(y-1)^{n-m}sumlimits_{(sum a_i)=n}frac{n!}{prod_{i=1}^m a_i!}prod a_i^{a_i-2}frac {1}{m!}(n^{m-2}prod_{i=1}^m a_i)^2\ =(y-1)^n n^{-4} n!sumlimits_{(sum a_i)=n}frac {1}{m!}{prod_{i=1}^m frac{n^2 a_i^{a_i}}{a_i!(y-1)}}\ ]

之需要考虑 (F_n=sumlimits_{(sum a_i)=n}frac {1}{m!}{prod_{i=1}^m frac{n^2 a_i^{a_i}}{a_i!(y-1)}}​) 的结果即可。

若设大小为 $k $ 的部分的贡献为 (G(k)=frac{n^2 k^k}{k! (y-1)})，考虑 (e^x) 即 (exp(x)) 的泰勒展开式为 (sum_{i=0}^{+INF} frac{x^i}{i!}) 。

有 (F=exp(G)) ，那么多项式求 (exp) 即可。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int read(){
	int nm=0,fh=1; char cw=getchar();
	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
	return nm*fh;
}
#define pii pair<int,int>
#define mp make_pair
#define mod 998244353
#define M 600010
namespace  CALC{
	inline int add(int x,int y){x+=y;return (x>=mod)?(x-mod):x;}
	inline int mns(int x,int y){x-=y;return (x<0)?(x+mod):x;}
	inline int mul(LL x,LL y){return (LL)x*(LL)y%mod;}
	inline void upd(int &x,int y){x+=y;(x>=mod)?(x-=mod):0;}
	inline int qpow(int x,int sq){
		int res=1;
		for(;sq;sq>>=1,x=mul(x,x)) if(sq&1) res=mul(res,x);
		return res;
	}
}using namespace CALC;
namespace POLY{
	int lg[M],g[40],v[40],od[M],iv[40],vv[M];
	void init(int N){
		N<<=2; int len=2,nw=1;
		for(;len<=N;len<<=1,nw++)
			lg[len]=nw,v[nw]=qpow(g[nw]=qpow(3,(mod-1)/len),mod-2),iv[nw]=qpow(len,mod-2);
		for(int i=1;i<=len;i++) vv[i]=qpow(i,mod-2);vv[0]=0;
	}
	void NTT(int *x,int len,int kd){
		int bas=lg[len];
		for(int i=1;i<len;i++) od[i]=(od[i>>1]>>1)|((i&1)<<(bas-1));
		for(int i=1;i<len;i++) if(i<od[i]) swap(x[i],x[od[i]]);
		for(int tt=1,tp=1;tt<len;tp++,tt<<=1){
			for(int wn=(kd>0)?g[tp]:v[tp],st=0;st<len;st+=(tt<<1)){
				for(int now=1,pos=st;pos<st+tt;pos++,now=mul(now,wn)){
					int t1=x[pos],t2=mul(now,x[pos+tt]);
					x[pos]=add(t1,t2),x[pos+tt]=mns(t1,t2);
				}
			}
		} if(kd>0) return;
		for(int i=0;i<len;i++) x[i]=mul(x[i],iv[bas]);
	}
	inline void cpy(int *_dt,int *_ss,int len){memcpy(_dt,_ss,sizeof(int)*len);}
	void get_inv(int *F,int *G,int len){
		static int A[M],B[M];
		if(len==1){G[0]=qpow(F[0],mod-2);return;} get_inv(F,G,len>>1);
		cpy(A,F,len),cpy(B,G,len),len<<=1,NTT(A,len,1),NTT(B,len,1);
		for(int i=0;i<len;i++) G[i]=mns(add(B[i],B[i]),mul(mul(B[i],B[i]),A[i]));
		for(int i=0;i<len;i++) A[i]=B[i]=0; NTT(G,len,-1),len>>=1;
		for(int i=len;i<len+len;i++) G[i]=0;
	}
	inline void qd(int *F,int len){for(int i=1;i<len;i++) F[i-1]=mul(F[i],i); F[len-1]=0;}
	inline void jf(int *F,int len){for(int i=len-1;i;i--) F[i]=mul(F[i-1],vv[i]); F[0]=0;}
	void get_ln(int *F,int *G,int len){
		static int A[M],B[M];
		get_inv(F,A,len),cpy(B,F,len),qd(B,len),len<<=1;
		NTT(A,len,1),NTT(B,len,1);
		for(int i=0;i<len;i++) G[i]=mul(A[i],B[i]),A[i]=B[i]=0;
		NTT(G,len,-1),jf(G,len),len>>=1;
		for(int i=len;i<(len<<1);i++) G[i]=0;
	}
	void get_exp(int *F,int *G,int len){
		static int A[M],B[M];
		if(len==1){G[0]=1;return;} get_exp(F,G,len>>1);
		cpy(A,G,len),get_ln(G,B,len);
		for(int i=0;i<len;i++) B[i]=mns(F[i],B[i]);
		len<<=1,NTT(A,len,1),NTT(B,len,1);
		for(int i=0;i<len;i++) G[i]=mul(A[i],B[i]),A[i]=B[i]=0;
		NTT(G,len,-1),len>>=1;
		for(int i=len;i<len+len;i++) G[i]=0;
	}
}
int n,Y,op,ans,nts;
map<pii,bool> P;
namespace Q1{
	int fs[M],nt[M],to[M],tmp,F[M][2],K,vK,G[2];
	inline void link(int x,int y){nt[tmp]=fs[x],fs[x]=tmp,to[tmp++]=y;}
	inline void DP(int x,int last){
		F[x][0]=F[x][1]=K;
		for(int i=fs[x],v;i!=-1;i=nt[i]) if((v=to[i])^last){
			DP(to[i],x),G[0]=0,G[1]=0;
			for(int j=0;j<2;j++) for(int k=0;k<2;k++){
				if(!(j&k)) upd(G[j|k],mul(mul(F[x][j],F[v][k]),vK));
				if(k) upd(G[j],mul(F[x][j],F[v][k]));
			} F[x][0]=G[0],F[x][1]=G[1];
		}
	}
	inline int solve(){
		memset(fs,-1,sizeof(fs));
		for(int i=1,x,y;i<n;i++) x=read(),y=read(),link(x,y),link(y,x);
		if(Y==1) return qpow(n,n-2); K=mul(qpow(Y-1,mod-2),n),vK=qpow(K,mod-2),DP(1,0);
		return mul(mul(F[1][1],nts),mul(qpow(mul(n,n),mod-2),qpow(Y-1,n)));
	}
}
namespace Q2{
	int F[M],G[M];
	inline int solve(){
		if(Y==1) return qpow(n,n+n-4); int len=1,fc=1; POLY::init(n),F[0]=1;
		for(int i=1;i<=n;i++)
			F[i]=mul(mul(mul(n,n),mul(qpow(i,i),qpow(fc=mul(fc,i),mod-2))),qpow(Y-1,mod-2));
		while(len<=n) len<<=1; POLY::get_exp(F,G,len);
		return mul(mul(mul(G[n],fc),mul(nts,qpow(n,mod-1-4))),qpow(Y-1,n));
	}
}
int main(){
	//freopen("tree.in","r",stdin);
	//freopen("tree.out","w",stdout);
	n=read(),Y=read(),op=read(),nts=qpow(Y,n),Y=qpow(Y,mod-2);
	if(op==0){
		for(int i=1,x,y;i<n;i++) x=read(),y=read(),P[mp(x,y)]=P[mp(y,x)]=true;
		for(int i=1;i<n;i++) if(P.count(mp(read(),read()))) nts=mul(nts,Y);
		printf("%d
",nts); return 0;
	}
	if(op&1) printf("%d
",Q1::solve());
	else printf("%d
",Q2::solve());
	return 0;
}