P7929 [COCI2021-2022#1] Logičari
基环树 dp
基环树 dp 类似树形 dp，大致思路是把环断开，分类讨论之后树形 dp。
如果在树上做这题，设 \(f_{u,0/1,0/1}\) 表示考虑到 \(u\) 结点，\(u\) 结点否/是染色、\(fa_u\) 否/是染色的最小染色点数。转移有：
\(fa_u\) 被染色了，\(f_{u,0/1,1}=\sum f_{v,1,0/1}\)。
\(fa_u\) 没有被染色，这时候考虑 \(val=\sum f_{v,1,0/1}\)，枚举一个 \(v\) 点染色，\(f_{u,0/1,0}=\min(val-f_{v,0,0/1}+f_{v,1,0/1})\)。
在本题里，我们只需要额外讨论多出的一条边对点的染色情况的影响即可，这里需要多一些特判还需要把 dp 跑四次，分别固定了不同的染色情况。由于此题的状态较复杂，考虑用记忆化搜索跑 dp，更简洁。
建树操作用并查集维护。
复杂度 \(O(n\log n)\)，由于并查集。事实上，找环的操作可以 \(O(n)\)，只需要遍历时找到第一条非树边即可。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
int n, rt, rt2, rtc, rt2c;
i64 ans = iinf;
int fa[N], anc[N];
int find(int x) {
if(x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
struct node {
int to, nxt;
} e[N << 1];
int h[N], cnt;
void add(int u, int v) {
e[++cnt].to = v;
e[cnt].nxt = h[u];
h[u] = cnt;
}
i64 f[N][2][2];
void dfs(int u, int fa) {
anc[u] = fa;
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa) continue;
dfs(v, u);
}
}
int dp(int u, int col, int fac) {
if(f[u][col][fac] != -1) return f[u][col][fac];
bool vis = 1;
if(u == rt2 && col != rt2c) vis = 0;
if(u == rt2 && fac && rtc) vis = 0;
if(!vis) return f[u][col][fac] = iinf;
i64 ret = iinf, sum = col;
bool fg = 0; //记录此时儿子是否可以被染色
if(fac) fg = 1;
if(u == rt2 && rtc) fg = 1; //特判
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == anc[u]) continue;
sum += dp(v, 0, col);
}
if(fg) {
ret = std::min(ret, sum);
} else {
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == anc[u]) continue;
ret = std::min(ret, sum - dp(v, 0, col) + dp(v, 1, col));
}
}
return f[u][col][fac] = ret;
}
void Solve() {
std::cin >> n;
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= n; i++) {
int u, v;
std::cin >> u >> v;
int fu = find(u), fv = find(v);
if(fu == fv) rt = u, rt2 = v;
else {
fa[fu] = fv;
add(u, v), add(v, u);
}
}
dfs(rt, 0);
memset(f, -1, sizeof(f)), rtc = 0, rt2c = 0;
dp(rt, rtc, rt2c);
ans = std::min(ans, f[rt][rtc][rt2c]);
memset(f, -1, sizeof(f)), rtc = 0, rt2c = 1;
dp(rt, rtc, rt2c);
ans = std::min(ans, f[rt][rtc][rt2c]);
memset(f, -1, sizeof(f)), rtc = 1, rt2c = 0;
dp(rt, rtc, rt2c);
ans = std::min(ans, f[rt][rtc][rt2c]);
memset(f, -1, sizeof(f)), rtc = 1, rt2c = 1;
dp(rt, rtc, rt2c);
ans = std::min(ans, f[rt][rtc][rt2c]);
if(ans == iinf) std::cout << "-1\n";
else std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}