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代码

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