之前写那个（Luogu 2279） [HNOI2003]消防局的设立的时候暴力推了一个树形dp，然后就导致这个题不太会写。
贪心，先把树建出来，然后考虑按照结点深度排个序，每次取出还没有被覆盖掉的深度最大的结点的第$k$个祖先进行染色，这样子算到的答案一定是最小值。
考虑一个深度很大的结点一定要被覆盖掉，所以可以考虑自下向上进行统计，对应了按照深度排序的条件，而一个点是否要设立军队计算入答案和它深度最大的儿子有关，所有每次贪心地区覆盖就是对的。
要注意覆盖的时候并不是只向下的，向上也应该被覆盖，所以要记录一下判一下一个节点是否在栈中，而不是不能等于父亲。
不会算时间复杂度QωQ。
好像是POI一道原题的弱化版（Luogu 3479 [POI2009]GAS-Fire Extinguishers）
Code：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1e5 + 5; int n, k, tot = 0, head[N], ans = 0, fa[N], dep[N], a[N]; bool vis[N], ins[N]; struct Edge { int to, nxt; } e[N << 1]; inline void add(int from, int to) { e[++tot].to = to; e[tot].nxt = head[from]; head[from] = tot; } inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > ‘9‘ || ch < ‘0‘; ch = getchar()) if(ch == ‘-‘) op = -1; for(; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } bool cmp(const int x, const int y) { return dep[x] > dep[y]; } void dfs(int x, int fat, int depth) { fa[x] = fat, dep[x] = depth; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(y == fat) continue; dfs(y, x, depth + 1); } } void cov(int x, int dis) { if(dis < 0) return; vis[x] = ins[x] = 1; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; // if(y == fa[x]) continue; if(!ins[y]) cov(y, dis - 1); } ins[x] = 0; } inline void solve() { for(int i = 1; i <= n; i++) a[i] = i; sort(a + 1, a + 1 + n, cmp); /* for(int i = 1; i <= n; i++) printf("%d ", a[i]); printf("\n"); */ for(int i = 1; i <= n; i++) { int x = a[i]; if(vis[x]) continue; for(int j = k; j >= 1; j--, x = fa[x]); cov(x, k); ans++; } } int main() { read(n), read(k); int t; read(t); for(int x, y, i = 1; i < n; i++) { read(x), read(y); add(x, y), add(y, x); } dfs(1, 1, 1); /* for(int i = 1; i <= n; i++) printf("%d ", dep[i]); printf("\n"); */ solve(); printf("%d\n", ans); return 0; }
原文：https://www.cnblogs.com/CzxingcHen/p/9537493.html
