自动搬运

查看原文

来自洛谷，原作者为

	Programmeryhl 中正自守 其介如石

搬运于2025-08-24 23:16:55，当前版本为作者最后更新于2025-08-19 17:17:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简介

给定一棵树，在每个叶子节点和根节点之间添加连边，求删除一些边后能形成多少种不同的树。

思路

考虑动态规划，设 $dp_{i,1/0}$ 表示在以 $i$ 为根的子树中是/否使用“叶子”边的方案数。

对于 $u \rightarrow v$，自下而上地更新 $dp$ 值，可分为两种情况：

• 若不删去 $u \rightarrow v$ 这条边，$dp_{u,0}$ 仅有一种贡献来源即 $dp_{u,0}=dp_{u,0} \times dp_{v,0}$，而 $dp_{u,1}$ 有两种选择，分别是将“叶子”边接在 $u$ 的别的孩子上或接在 $v$ 的子树上，也就是 $dp_{u,1}=dp_{u,1} \times dp_{v,0} + dp_{u,0} \times dp_{v,1}$。

• 若删去 $u \rightarrow v$ 这条边，则 $dp_{u,0}=dp_{u,0} \times dp_{v,1}$，此时 $u$ 的别的孩子与 $v$ 的子树上均可以接“叶子”边，有 $dp_{u,1}=dp_{u,1} \times dp_{v,1}$。

时间复杂度显然 $O(n)$。

Code

#include<iostream>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=2e5+5;
const int MOD=998244353;
int n,head[N],nxt[N<<1],to[N<<1],cnt=0;
long long dp[N][2];
void add(int u,int v)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
void dfs(int u,int father)
{
	if(father) dp[u][0]=1;
	int son=0;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==father) continue;
		son++;
		dfs(v,u);
		dp[u][1]=(dp[u][1]*dp[v][0]%MOD+dp[u][0]*dp[v][1]%MOD+dp[u][1]*dp[v][1]%MOD)%MOD;
		dp[u][0]=(dp[u][0]*dp[v][0]%MOD+dp[u][0]*dp[v][1]%MOD)%MOD;
	}
	if(!son) dp[u][0]=dp[u][1]=1;
}
int main()
{
	IOS;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v),add(v,u);
	}
	dp[1][1]=1;
	dfs(1,0);
	cout<<max(dp[1][1],dp[1][0])<<'\n';
	return 0;
}