# [USACO18JAN] Cow at Large G

题意：

给定一个迷宫，构成一棵有根树，你开始在根节点，出口是每个叶子节点， $\text{L}$ 可以在每个出口放一个守卫，每 1个 单位时间内，你和守卫都可以移动到相邻的一个点，如果某一时刻守卫与你相遇了（在边上或点上均算），则你将被抓住。问为了保证抓住你， $\text{L}$ 最少需要几个守卫。

解法：
在你屁股后面追的永远都追不上你，所以只用考虑往前走，对于一个节点 $i$ ，如果这个在 $i$ 的子树中中距离 $i$ 最近的叶子节点，能在我们到达之前到达，那么我们肯定不会往这个节点走，相当于一个守卫守住了一棵子树。按照这个思想两边 $\text{DFS}$ 就做啦。

Code

	#include <iostream>
	#include <algorithm>
	#include <cstring>
	#include <cstdio>
	#include <cmath>
	#include <map>
	#include <queue>
	#include <stack>
	#include <set>
	#include <iomanip>
	using namespace std;
	const int MAXN=1e6+10;
	struct edge{
	int nex,to;
	}p[MAXN];
	vector<int> qtree;
	int cnt,head[MAXN],dep[MAXN],dis[MAXN],ans;
	void add(int from,int to){
	p[++cnt]=edge{head[from],to};
	head[from]=cnt;
	}
	void dfs(int now,int fa){
	dep[now]=dep[fa]+1;
	bool fla=false;
	for(int i=head[now];i;i=p[i].nex){
	int to=p[i].to;
	if(to==fa){
	continue;
	}
	dfs(to,now);
	fla=true;
	if(dis[now]==0){
	dis[now]=dis[to]+1;
	}else{
	dis[now]=min(dis[to]+1,dis[now]);
	}
	}
	if(!fla){
	qtree.push_back(now);
	}
	}
	void dfs2(int now,int fa){
	for(int i=head[now];i;i=p[i].nex){
	int to=p[i].to;
	if (to==fa){
	continue;
	}
	if(dep[to]-1>=dis[to]){
	ans++;
	}else{
	dfs2(to,now);
	}
	}
	}
	int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<n;i++){
	int x,y;
	cin>>x>>y;
	add(x,y);
	add(y,x);
	}
	dfs(m,0);
	dfs2(m,0);
	cout<<ans;
	}