洛谷 P4186

首先对于一棵子树，肯定是放在这棵子树中深度最小的叶节点。
那如何分析子树中深度最小的叶节点深度够不够小呢？
我们看到，我们关注叶节点深度是为了看它能不能在 Bessie 从根节点到达该子树的根之前（或同时）到达子树的根。
也就是说，最浅叶节点 到 子树根 的距离应该小于等于 树根 到 子树根 的距离。只要满足了这一点，该子树就可以只放一个农民。否则我们就要继续递归去考虑这个子树的各个子树。
DFS 求出每个节点的深度以及以它为根的子树的最浅叶节点的深度。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, k, ans;
int head[N], ver[N*2], nxt[N*2], cnt;
int dep[N], mn[N];

void add(int u, int v) {
	ver[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}

void dfs(int u, int fa) {
	int t = dep[u];
	for (int i = head[u]; i; i = nxt[i]) {
		int v = ver[i];
		if (v == fa) continue;
		dep[v] = dep[u] + 1, dfs(v, u);
		if (t == dep[u]) t = mn[v];
		else t = min(t, mn[v]); 
	}
	mn[u] = t;
}

void dfs1(int u, int fa) {
	if (mn[u] <= dep[u] * 2) return ++ans, void();
	for (int i = head[u]; i; i = nxt[i]) {
		int v = ver[i];
		if (v == fa) continue;
		dfs1(v, u); 
	}
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), add(u, v), add(v, u);
	dfs(k, 0), dfs1(k, 0);
	printf("%d", ans);
	return 0;
}