Codeforces Gym101667 A. Broadcast Stations
题意：
给定一棵树，可以选定一些点在上面放基站。
若节点\(u\)上的基站（如果有的话）的辐射范围为\(d\)，那么距离\(u\)小于等于\(d\)的点会被覆盖。放一个辐射范围为\(d\)的基站需要花费\(d\)。
问：使得整棵树被覆盖的最小花费。
分析：
尝试进行动态规划。
我们很自然地考虑以\(u\)为根的树被完全覆盖的情况，设\(u\)有子节点\(v_1,v_2,\dots,v_m\)。如果令\(f(u)\)为以\(u\)为根节点的树被覆盖的最小花费，就需要考虑\(f(u)\)可以怎样由子节点推出。这本质上就是考虑\(u\)处放不放基站，以及放辐射范围为多少的基站。我们发现，要覆盖\(u\)有两种类型，一种是\(u\)本身放基站，另一种是以子节点为根节点的树的覆盖范围延伸到\(u\)节点。这个时候我们会发现\(f(u)\)这个状态定义太“粗”了，需要细化。
为了细化状态，我们可以考虑这样定义，令\(f(u,d)\)为以\(u\)为根的树被完全覆盖且对于\(u\)还至少能够继续延伸距离\(d\)的范围的最小花费，换句话说\(f(u,d)\)是以\(u\)为根的树被完全覆盖且距离\(u\)小于等于\(d\)的点被全部覆盖的最小花费，这样可以看出\(f(u,d)\)和\(f(v,d+1)\)相关。然而我们发现就算是这样还是不够，为什么呢？因为对于以\(u\)的子节点为根的树而言是可以通过父节点\(u\)相互延伸的，而且\(u\)节点也能够延伸到以其子节点为根的树。此时部分子树就不需要完全覆盖，只需要覆盖某个地方以下的部分即可。
为了解决这个问题，我们需要定义另一个状态，令\(g(u,d)\)为在以\(u\)为根节点的树的内部，距离\(u\)大于等于\(d\)的节点被全部覆盖的最小花费。这样就可以写出具体的状态转移了。
尤其注意第\(3\)个和第\(4\)个式子（边界的情况）
第\(3\)个式子不存在父亲上放基站延伸到以子节点为根的树的情况。
第\(4\)个式子不能遗漏。
注意到\(\sum\limits_{i=1}^mg(v_i,d)=g(u,d+1)\)，以及\(\sum\limits_{1\leq j\leq m\and i\neq j}g(v_j,d)=g(u,d+1)-g(v_i,d)\)
且对于叶节点，\(f(u,d)=d(d\geq1)\)，\(f(u,0)=1\)，\(g(u,d)=0(d\geq1)\)，\(g(u,0)=1\)
所以转移部分，转化成代码可以写成
for (auto v : G[u]) {
if (v == fa) continue;
for (int d = 1; d < n; d++) {
// 先不用急着取最小值（事实上也不能，因为g[u][0]还不知道）
// 只计算和，运算结果对计算f[u][d]有帮助
g[u][d] += g[v][d - 1];
}
}
f[u][n - 1] = n - 1;
for (int d = n - 2; d >= 0; d--) {
if (d > 0) f[u][d] = min(f[u][d + 1], d + g[u][d + 1]);
else f[u][0] = f[u][1];
for (auto v : G[u]) {
if (v == fa) continue;
f[u][d] = min(f[u][d], f[v][d + 1] + g[u][d + 1] - g[v][d]);
}
}
g[u][0] = f[u][0];
for (int d = 1; d < n; d++) g[u][d] = min(g[u][d - 1], g[u][d]);
代码：
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 5000 + 10;
vector<int> G[maxn];
int f[maxn][maxn], g[maxn][maxn];
int n;
void dfs(int u, int fa) {
for (auto v : G[u]) {
if (v == fa)
continue;
dfs(v, u);
for (int d = 1; d < n; d++)
g[u][d] += g[v][d - 1];
}
f[u][n - 1] = n - 1;
for (int d = n - 2; d >= 0; d--) {
if (d > 0)
f[u][d] = min(f[u][d + 1], d + g[u][d + 1]);
else
f[u][0] = f[u][1];
for (auto v : G[u]) {
if (v == fa)
continue;
f[u][d] = min(f[u][d], f[v][d + 1] + g[u][d + 1] - g[v][d]);
}
}
g[u][0] = f[u][0];
for (int d = 1; d < n; d++)
g[u][d] = min(g[u][d - 1], g[u][d]);
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
printf("%d\n", g[1][0]);
return 0;
}