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