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;
}