将每个独立集$V$考虑为原图中被染色的一些顶点，而在原图中加边后$E'$可以得到一个子图$G'$，这个子图如果满足一些条件，$V$就是$E'$生成的子图$G'$中的一个独立集。这些条件为：
- 一条边的两端不同时被染色（或$V$中任意两点间没有边）
- 没有孤立顶点被染色（$V$中的每个点都应当与$E'$中的一条边相连）
这样问题就转化为了：对每个点集，得出可行的加边方案数。
这种操作可以由子图转移到大图上，可以由树形DP来完成。定义状态：
dp[u][0]: 以u为根的子树（看作一个图）上，$u\notin V$的情况总数
dp[u][1]: 以u为根的子树上，$u\in V$的情况总数
dp[u][2]: 以u为根的子树上，u染色且不与任一儿子连边的情况
上面的"情况"都指除u外所有点都不孤立的情况。dp[u][2]是指$u$为被染色的孤立点的情况。
下面考虑转移方程。假设对$u$的每个儿子$v$，都已知dp[v][0]，dp[v][1]，dp[v][2]。那么
- $dp[u][0]=\Pi_{v}(2dp[v][0]+2dp[v][1]-dp[v][2])$
- $dp[u][1]=\Pi_{v}(2dp[v][0]+dp[v][1]-dp[v][2])$
- $dp[u][2]=\Pi_{v}(dp[v][0]+dp[v][1]-dp[v][2])$
第一个方程的意思是：对每个儿子v中合法（除v外全不孤立）的每种情况，可以选择v与u连接和不与u连接，会得到两种不同的子图，并且它们都合法，情况总数为$2dp[v][0]+2dp[v][1]$，除了v孤立并被染色且不与u连接（在以v为根的子树中）的情况，这种情况总数为$dp[v][2]$。
第二个方程的意思是：对每个儿子v，由于u被染色，从而v不被染色的情况可以选择与u连接和不与u连接，总数为$2dp[v][0]$，而v被染色的情况只能选择不与u连接，总数为$dp[v][1]$，但v被染色且不与u连接的情况可能包含v孤立的情况，从而需要减去$dp[v][2]$。
第三个方程的意思是：u被染色且每个儿子v都不与u连边，从而$dp[v][0]$和$dp[v][1]$都只能做1次贡献，因为他们不能选择是否与u连接。v仍然不能孤立，所以需要减去$dp[v][2]$。
现在考虑边界情况，一个是叶子节点，一个是根节点。
对叶子节点，直接考虑意义即可得知dp[u][0]=dp[u][1]=dp[u][2]=1。
对根节点，总情况个数为：
dp[u][0]+dp[u][1]-dp[u][2]-1
这个式子的意思是：选u和不选u均可，选u就要去掉u孤立的情况，即dp[u][2]，不选u就要去掉空集（是指无边，而非无染色顶点：无染色顶点在很多子图中都是一个独立集）的情况，因为题目禁止$E=\varnothing$。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <vector>
#define maxn 300005
#define MOD 998244353LL
using namespace std;
typedef long long ll;
ll dp[maxn][3];
vector<int> G[maxn];
bool vis[maxn];
void dfs(int i);
int main() {
int n;
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n;
int a, b;
for (int i = 0; i < n - 1; i++) {
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
dfs(1);
cout << ((dp[1][0] + dp[1][1] - dp[1][2] - 1LL + 100 * MOD) % MOD) << endl;
return 0;
}
void dfs(int u) {
vis[u] = true;
dp[u][0] = dp[u][1] = dp[u][2] = 1;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (vis[v]) continue;
dfs(v);
dp[u][0] = (dp[u][0] * (2 * dp[v][0] + 2 * dp[v][1] - dp[v][2]) + 100 * MOD) % MOD;
dp[u][1] = (dp[u][1] * (2 * dp[v][0] + dp[v][1] - dp[v][2]) + 100 * MOD) % MOD;
dp[u][2] = (dp[u][2] * (dp[v][0] + dp[v][1] - dp[v][2]) + 100 * MOD) % MOD;
}
}
|