洛谷 P3523 [POI2011] DYN-Dynamite
分析
二分答案,问题转化为:对于给定的 \(K\),选择尽可能少的节点,使得所有关键节点都被「覆盖」。
对于一个关键节点,「覆盖」的定义为:存在一个被选择的点与这个关键节点的距离不大于 \(K\)。
方便起见,我们指定 \(1\) 号节点是这棵树的根节点。
我们使用树形 DP 的思路,自底而上、无后效性地求解。换句话说,显然地,当我们考虑一个节点 \(u\) 时,默认 \(u\) 的子树内已经达到最优。
对于每个节点 \(u\),我们维护两个信息:
-
\(f _ u\):\(u\) 的子树内离 \(u\) 最远的 未被覆盖的关键节点 和 \(u\) 之间的距离。特别地,若 \(u\) 的子树内不存在 未被覆盖的关键节点,则 \(f _ u = -\infty\)。
-
\(g _ u\):\(u\) 的子树内离 \(u\) 最近的 被选择的节点 和 \(u\) 之间的距离。特别地,若 \(u\) 的子树内不存在 被选择的节点,则 \(g _ u = \infty\)。
初始化 \(f _ u = - \infty, g _ u = \infty\),然后从 \(u\) 的儿子节点转移:
现在我们对儿子节点的信息进行汇总:
- 若 \(f _ u + g _ u \le K\),那么 \(u\) 的子树内所有关键节点都被覆盖了,更新 \(f _ u \gets -\infty\)。
- 若 \(d _ u = 1\),\(u\) 本身是一个关键节点,更新 \(f _ u \gets \max \{f _ u, 0\}\)。
接下来决策要不要选择 \(u\),我们有贪心结论:当且仅当 \(f _ u = K\) 时选择 \(u\)。
略证:必要性显然;充分及最优性则是因为若 \(f _ u < K\) 我们就可以选择 \(u\) 的祖先,而 \(u\) 的祖先一定不比 \(u\) 劣,因为 \(u\) 的祖先可以覆盖更大的范围。
当然 $u = 1 $ 是个例外,根节点没有祖先,所以若 \(f _ 1 \ne -\infty\) 就一定要选 \(1\) 号节点。
如果选择了 \(u\),那么同样也要更新:
总结一下:在 \([0, n]\) 内二分 \(K\),每次判定时自底而上维护、决策,记录选择了几个点。
复杂度分析
二分复杂度为 \(\operatorname{O}(\log n)\),每次树形 DP 判定复杂度为 \(\operatorname{O}(n)\),总时间复杂度为 \(\operatorname{O}(n \log n)\)。
实现
递归常数略大,可能需要卡常。
#include <iostream>
#include <vector>const int N = 300'000, INF = 1e9;int n, m, cnt;
bool d[N + 5];
int f[N + 5], g[N + 5];
std::vector<int> edge[N + 5];void dfs(int u, int fa, int k)
{f[u] = -INF;g[u] = INF;for (auto v : edge[u])if (v != fa){dfs(v, u, k);f[u] = std::max(f[u], f[v] + 1);g[u] = std::min(g[u], g[v] + 1);}if (f[u] + g[u] <= k)f[u] = -INF;if (d[u] && g[u] > k)f[u] = std::max(f[u], 0);if (f[u] == k){f[u] = -INF;g[u] = 0;cnt++;}
}bool check(int k)
{cnt = 0;dfs(1, 0, k);if (f[1] >= 0)cnt++;return cnt <= m;
}int binary_search()
{int l = 0, r = n, res = 0;while (l <= r){int mid = (l + r) / 2;if (check(mid)){r = mid - 1;res = mid;}elsel = mid + 1;}return res;
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cin >> n >> m;for (int i = 1; i <= n; i++)std::cin >> d[i];for (int i = 1; i < n; i++){int u, v;std::cin >> u >> v;edge[u].push_back(v);edge[v].push_back(u);}std::cout << binary_search() << "\n";return 0;
}