Preface

随机跳题做到了这道。

题目

https://www.luogu.com.cn/problem/P2899

题解

其实就是交叉染色。我们考虑每棵子树的情况。设 f[u] 表示以 u 为根的最小答案。三种子情况:

  • f[u][0]: u 自己本身被染色
  • f[u][1]: u 的某个儿子染色了,使之被覆盖进了范围
  • f[u][2]: u 的父亲染色了,使之被覆盖进了范围

接下来是转移方程:

f[u][0]=1+vu.sonmin{f[v][0],f[v][1],f[v][2]}

f[u][1]=minxu.son(f[x][0]+vu.son{x}min{f[v][0],f[v][1]})

f[u][2]=vu.sonmin{f[v][0],f[v][1]}

我们会发现如果上暴力的话,第二个转移方程的复杂度是 O(n2),我们不妨简单地优化一下。第二个方程的主要含义是枚举哪个儿子必须要被染色,使之覆盖到父亲。那么很简单,假设如果那个染色的儿子是 x,然而却有一个更好的儿子 y 使得代价更小,那么必然有:

f[x][0]+vu.son{x}min{f[v][0],f[v][1]}>f[y][0]+vu.son{y}min{f[v][0],f[v][1]}

化简一下:

f[x][0]min{f[x][0],f[x][1]}>f[y][0]min{f[y][0],f[y][1]}

这个复杂度是 O(n)

代码

#include <iostream> using namespace std; const int maxn = 2e4+5; // [u][0] -> u // [u][1] -> son // [u][2] -> fa int n, head[maxn], f[maxn][3], ecnt = 2; struct edge { int to, next; } g[maxn]; void add_edge(int u, int v) { g[ecnt] = (edge) {v, head[u]}; head[u] = ecnt ++; } void dfs(int u, int fa) { f[u][0] = 1; int x = 0; for (int e = head[u]; e; e = g[e].next) { int v = g[e].to; if (v == fa) continue; dfs(v, u); f[u][0] += min(min(f[v][0], f[v][1]), f[v][2]); f[u][2] += min(f[v][0], f[v][1]); if (f[x][0] - min(f[x][0], f[x][1]) > f[v][0] - min(f[v][0], f[v][1])) x = v; } f[u][1] = f[x][0]; for (int e = head[u]; e; e = g[e].next) { int v = g[e].to; if (v == fa) continue; if (v == x) continue; f[u][1] += min(f[v][0], f[v][1]); } } int main() { cin >> n; for (int i = 1; i < n; i ++) { int u, v; cin >> u >> v; add_edge(u, v); add_edge(v, u); } f[0][0] = 2e9; dfs(1, 0); cout << min(f[1][0], f[1][1]) << endl; return 0; }
C
最后修改:2022 年 03 月 24 日 12 : 27 AM
真的不买杯奶茶嘛....qwq