C. Vertex Deletion (树形dp)

C. Vertex Deletion

题目链接

大致题意:

给出一个树,包含n个点,n-1条无向边.合法删点:删除一个点后,剩余的每个点都至少有一个点与其相连.

求有多少合法的删点方案(mod 998244353)

解题思路:

树形dp+01背包的思想(删或不删)

状态转移过程中,我们只对子树进行分析,对于u点,用到了01背包的思想,该点删or不删,我们分三种状态:

1.删除u点,(子树内节点全部满足条件的方案)

2.不删除u点,但u点的儿子中至少有一个点与u点相连,(子树内节点全部满足条件的方案)

3.不删除u点,但u点的儿子中没有点与u点相连,(子树内节点全部满足条件的方案)

状态表示可以写成f[i][0|1|2]

转移方程:

f [ u ] [ 0 ] = ∏ v ∈ s o n u ( f [ v ] [ 0 ] + f [ v ] [ 2 ] ) f[u][0] = \prod \limits_{v \in son_u} (f[v][0] + f[v][2]) f[u][0]=v∈sonu​∏​(f[v][0]+f[v][2]) 删除u点,对于u的子节点,我们可以删,可以不删,两种状态都可以转移

f [ u ] [ 2 ] = ∏ v ∈ s o n u f [ v ] [ 0 ] f[u][2] = \prod \limits_{v \in son_u} f[v][0] f[u][2]=v∈sonu​∏​f[v][0] 不删除u点,且u点不与其子节点连接,只能是其子节点删除这一种状态可以转移

f [ u ] [ 1 ] = ∏ v ∈ s o n u ( f [ v ] [ 0 ] + f [ v ] [ 1 ] + f [ v ] [ 2 ] ) − ∏ v ∈ s o n u f [ v ] [ 0 ] f[u][1] = \prod \limits_{v \in son_u} (f[v][0] + f[v][1] + f[v][2]) -\prod \limits_{v \in son_u} f[v][0] f[u][1]=v∈sonu​∏​(f[v][0]+f[v][1]+f[v][2])−v∈sonu​∏​f[v][0] 对于f[u][1]来说,情况复杂,但是我们可以考虑用容斥原理,即 只与一个子节点相连的情况=所有的情况-与所有子节点不相连的情况

最终答案就是 f [ 1 ] [ 0 ] + f [ 1 ] [ 1 ] f[1][0]+f[1][1] f[1][0]+f[1][1]

注意:取模

AC代码:

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 998244353;
int n, m;
ll f[N][3];
vector<int>e[N];

void dfs(int u, int fa) {
	f[u][0] = f[u][1] = f[u][2] = 1;
	for (auto& v : e[u]) {
		if (v == fa)continue;
		dfs(v, u);
		f[u][0] = (f[v][0] + f[v][1]) % mod * f[u][0] % mod;
		f[u][2] = f[u][2] * f[v][0] % mod;
		f[u][1] = (f[v][0] + f[v][1] + f[v][2]) % mod * f[u][1] % mod;
	}
	f[u][1] = (f[u][1] - f[u][2]) % mod;
}

int main(void)
{
	int t; scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i)e[i].clear();

		for (int i = 1; i < n; ++i) {
			int a, b; scanf("%d %d", &a, &b);
			e[a].push_back(b); e[b].push_back(a);
		}

		dfs(1, 0);
		ll res = ((f[1][0] + f[1][1]) % mod + mod) % mod;
		printf("%lld\n", res);
	}
	return 0;
}