526互联

Atcoder Grand Contest 058 F - Authentic Tree DP

发布时间 2023-08-07 16:54:37作者: tzc_wk

考虑给 \(f(T)\) 赋予组合意义。一个直观的想法是，在每条边中间新建一个节点，然后每次选择一条边对应的点，然后把它删掉，递归剩余的两个部分，但是你会发现这样分母不对，应该是 \(n\) 但在这个模型里只有 \(n-1\)。

考虑魔改这个模型。我们在每个边对应的点下面添加 \(998244352\) 个点，你发现这样总点数 \(\bmod 998244353\) 就等于 \(n\)。于是 \(f(T)\) 实际上就是这样一个东西：

设得到的数中有 \(k\) 个节点，那么考虑将 \(1\sim k\) 随机填入这棵树的 \(k\) 个节点中，有多大概率满足每条边所对应的点小于它所有的邻居。

考虑容斥，即我们钦定一些边点大于它的父亲，容斥系数为 \((-1)^{\text{钦定的边点个数}}\)，这样考虑从每个边点向其所有儿子连边，对于那些钦定的边点，从其父亲向这个边点本身连边，那这种情况的概率就是 \(\prod\dfrac{1}{siz_i}\)。这样就可以树上背包了，设 \(dp_{i,j}\) 表示考虑 \(i\) 子树中的点，目前以 \(i\) 为根的部分的 \(siz\equiv j\pmod{998244353}\) 的概率乘以容斥系数之和。转移见代码。时间复杂度 \(O(n^2)\)。

const int MAXN=5000;
const int MOD=998244353;
int n,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int dp[MAXN+5][MAXN+5],siz[MAXN+5],res,inv[MAXN+5];
void dfs(int x,int f){
	dp[x][siz[x]=1]=1;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e];if(y==f)continue;dfs(y,x);
		static int tmp[MAXN+5];memset(tmp,0,sizeof(tmp));
		int sum=0;
		for(int i=1;i<=siz[y];i++)sum=(sum+1ll*inv[i]*inv[i]%MOD*dp[y][i])%MOD;
		for(int i=1;i<=siz[x];i++)for(int j=1;j<=siz[y];j++)
			tmp[i+j]=(tmp[i+j]+1ll*dp[x][i]*dp[y][j]%MOD*inv[j]%MOD*inv[j])%MOD;
		siz[x]+=siz[y];
		for(int i=1;i<=siz[x];i++)dp[x][i]=(1ll*sum*dp[x][i]-tmp[i]+MOD)%MOD;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=(inv[0]=inv[1]=1)+1;i<=n;i++)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
	dfs(1,0);for(int i=1;i<=n;i++)res=(res+1ll*dp[1][i]*inv[i])%MOD;
	printf("%d\n",res);
	return 0;
}