CF630D2F

将每个独立集$V$考虑为原图中被染色的一些顶点, 而在原图中加边后$E'$可以得到一个子图$G'$, 这个子图如果满足一些条件, $V$就是$E'$生成的子图$G'$中的一个独立集。这些条件为:

  1. 一条边的两端不同时被染色 (或$V$中任意两点间没有边)
  2. 没有孤立顶点被染色 ($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;
	}
}