D - Deterministic Placing

一个很难的题目 写个博客加深印象.

首先可以把树划分成许多链 每个链可以分为0端和1端 有三个结论(可证).

1.0端和0端不能在一起

2.1端和1端不能在一起

3.中间点不能和别的端点在一起

除此之外其他都是合法的.

so,把链划分dp转移可以得到答案.

定义dp状态:

0:表示为中间点 端点两个在子树内

1:表示为中间点 端点一个在子树内

2:表示为端点 端点不在子树内

3:表示为端点 端点在子树内

0/1端可以划分连通块 但是并不是一条链就是一个联通块 什么情况下才会产生边划分呢?显然端点相连不能产生连通块划分,只能属于两个不同的中间点相连才可以,我们把较高出的中间点进行划分.

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=2e5+5;
const int M=4;
const int mod=998244353;

vector<int>G[N];
ll suf[N],f[N][M],dp[N][M];

ll qp(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1)	res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

void dfs(int u,int fa)
{
	vector<int>son;
	for(int v:G[u])
	{
		if(v==fa)	continue;
		dfs(v,u); 
		son.push_back(v);
	}
	int sz=(int)son.size();
	//2
	f[u][2]=1;
	if(sz==0)	return;
	for(int i=0;i<sz;i++)
		f[u][2]=f[u][2]*f[son[i]][3]%mod;
	//3
	suf[sz]=1;
	for(int i=sz-1;i>=0;i--)	suf[i]=suf[i+1]*f[son[i]][3]%mod;
	ll base=1;
	for(int i=0;i<sz;i++)
	{
		f[u][3]+=(f[son[i]][1]+f[son[i]][2])*base%mod*suf[i+1]%mod,f[u][3]%=mod;
		base=base*f[son[i]][3]%mod;
	}
	//1 1只能和f[son[i]][0]连接 自己这个可以连f[son[i]][1/2].
	suf[sz]=1; 
	for(int i=sz-1;i>=0;i--)	suf[i]=suf[i+1]*f[son[i]][0]%mod;
	base=1;
	for(int i=0;i<sz;i++)
	{
		f[u][1]+=(f[son[i]][1]+f[son[i]][2])*base%mod*suf[i+1]%mod,f[u][1]%=mod;
		base=base*f[son[i]][0]%mod;
	}
	for(int i=0;i<sz;i++)
	{
		for(int j=0;j<3;j++)
		{
			if(i==0)		
			{
				if(j==0)		dp[i][j]=f[son[i]][0];
				else if(j==1)	dp[i][j]=(f[son[i]][1]+f[son[i]][2])%mod;
			}
			else if(j==0)	dp[i][j]=dp[i-1][j]*f[son[i]][0]%mod;
			else			dp[i][j]=(dp[i-1][j]*f[son[i]][0]%mod+dp[i-1][j-1]*(f[son[i]][1]+f[son[i]][2])%mod)%mod;
		}
	}
	f[u][0]=dp[sz-1][2];
	ll cnt=sz-2;
	if(cnt>0)	f[u][0]=f[u][0]*qp(2ll,cnt)%mod;
	cnt++;
	if(cnt>0)	f[u][1]=f[u][1]*qp(2ll,cnt)%mod;
}

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,1);
	cout<<(f[1][0]+f[1][3])*2ll%mod<<'\n';
	return 0;
}