题目
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1903
题意
一棵树，根上有VOD站，要求任意叶节点到VOD站的距离不超过k，问最少建新VOD站数。
思路
1. 令vod[i]为节点i到VOD站的最短距离， 注意，这是在以i为根的树上有VOD站的情况下，如果没有，vod[i]就设为非法。
依据树形DP的思路，如果在该节点（非叶节点）建站，vod[i]=0，否则 vod[i] = min(vod[child] + 1) for child in i.children.（此时注意不要统计没有VOD的子树的非法值）
2. 令urge[i]为以i为根的树中有叶节点还没被满足的情况下，该节点能忍受VOD站在此树外的最远距离。注意如果所有叶节点都被满足了，urge[i]就设为非法。
对于叶节点, urge[i] = k，对于非叶节点，urge[i] = min(urge[child] + 1] for child in i.children)，（此时注意不要统计已经被满足的非法值）
3. 如何判断这棵树的孩子们之间有没有相互满足？明显，如果urge[i]和vod[i]都存在，且urge[i] <= vod[i]，则说明有兄弟相互满足的情况。
4. 如果孩子们之间无法相互满足？如果urge[i] > 0，说明不紧迫，交给父亲树去办。如果urge[i] = 0，说明需要建新站。
感想
1. 注意边是无向边，因此边数是点数2倍！
代码
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#define LOCAL_DEBUG
using namespace std;
const int MAXN = 2e3 + ;
const int inf = 0x3ffffff;
int n, k, s;
int vod[MAXN];
int urge[MAXN];
int first[MAXN];
int to[MAXN];
int nxt[MAXN];
int edgeNum; void addEdge(int f, int t) {
nxt[edgeNum] = first[f];
to[edgeNum] = t;
first[f] = edgeNum++;
} int dfs(int root, int fa) {
if (nxt[first[root]] == -) {
urge[root] = k;
vod[root] = inf;
return ;
}
int ans = ;
vod[root] = inf;
urge[root] = inf;
for (int p = first[root]; p != -; p = nxt[p]) {
int t = to[p];
if (t == fa)continue;
ans += dfs(t, root);
if (vod[t] != inf) {
vod[root] = min(vod[t] + , vod[root]);
}
if (urge[t] != inf) {
urge[root] = min(urge[t] - , urge[root]);
}
}
if (urge[root] != inf) {
if (vod[root] != inf && vod[root] <= urge[root]) {
urge[root] = inf;//satisfied
}
else if (urge[root] == && root != s) {
ans ++;
vod[root] = ;//set up a new one;
urge[root] = inf;//satisfied
}
}
return ans;
} int main() {
#ifdef LOCAL_DEBUG
freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
//freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
#endif // LOCAL_DEBUG
int T;
scanf("%d", &T);
for (int ti = ; ti <= T; ti++) {
memset(first, -, sizeof first);
edgeNum = ;
scanf("%d%d%d", &n, &s, &k);
for (int i = ; i < n; i++) {
int f, t;
scanf("%d%d", &f, &t);
addEdge(f, t);
addEdge(t, f);
}
int ans = dfs(s, -);
printf("%d\n", ans); } return ;
}