CF630D2F

将每个独立集 $$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代码

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

Wilson's blog: 博客!

AC代码