USACO Cow at Large

USACO Cow at Large

洛谷传送门

题目描述

最后，Bessie 被迫去了一个远方的农场。这个农场包含 NN 个谷仓（2 le N le 10^52≤N≤105）和 N-1N−1 条连接两个谷仓的双向隧道，所以每两个谷仓之间都有唯一的路径。每个只与一条隧道相连的谷仓都是农场的出口。当早晨来临的时候，Bessie 将在某个谷仓露面，然后试图到达一个出口。

但当 Bessie 露面的时候，她的位置就会暴露。一些农民在那时将从不同的出口谷仓出发尝试抓住 Bessie。农民和 Bessie 的移动速度相同（在每个单位时间内，每个农民都可以从一个谷仓移动到相邻的一个谷仓，同时 Bessie 也可以这么做）。农民们和Bessie 总是知道对方在哪里。如果在任意时刻，某个农民和 Bessie 处于同一个谷仓或在穿过同一个隧道，农民就可以抓住 Bessie。反过来，如果 Bessie 在农民们抓住她之前到达一个出口谷仓，Bessie 就可以逃走。

Bessie 不确定她成功的机会，这取决于被雇佣的农民的数量。给定 Bessie 露面的谷仓K，帮助 Bessie 确定为了抓住她所需要的农民的最小数量。假定农民们会自己选择最佳的方案来安排他们出发的出口谷仓。

输入格式

输入的第一行包含 NN 和 KK。接下来的 N – 1N–1 行，每行有两个整数（在 1sim N1∼N 范围内）描述连接两个谷仓的一条隧道。

输出格式

输出为了确保抓住 Bessie 所需的农民的最小数量。

由 @Marser 提供翻译

---

题解：

2020.11.12模拟赛满分场

%%%学弟TQL

一开始看到树上最优化想树形DP，后来发现推不出一个转移方程。觉得是不是自己想假了？后来开始手玩样例，发现一个性质：

按理讲，每个叶子节点都应该安排人去堵，但是不必要，因为只要有多个人是等效的，就只派一个人去收即可。

什么时候是等效的呢？

我们对于每个节点维护两个信息：第一个信息是deep[x]，牛最早能多早到达这个节点，其值就是深度-1。第二个信息是low[x]，最快到达这个节点的追的人最早能多早到达这个节点，其值可以深搜处理。很容易得出，如果low[x]<=deep[x]，这个点就被堵死了，但是这个点的贡献只是1，无论下面有多少叶子节点。

所以再深搜一遍，碰到堵死的节点就把ans++，再返回就可。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
const int INF=1e9;
int n,s;
int tot,head[maxn],nxt[maxn<<1],to[maxn<<1];
int fa[maxn],deep[maxn],low[maxn];
int du[maxn];
int ans;
void add(int x,int y)
{
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void dfs1(int x,int f)
{
	deep[x]=deep[f]+1;
	fa[x]=f;
	int tmp=INF;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==f)
			continue;
		dfs1(y,x);
		tmp=min(tmp,low[y]);
	}
	if(du[x]==1)
		low[x]=0;
	else
		low[x]=tmp+1;
}
void dfs2(int x)
{
	if(deep[x]>=low[x])
	{
		ans++;
		return;
	}
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa[x])
			continue;
		dfs2(y);
	}
}
int main()
{
	scanf("%d%d",&n,&s);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
		du[x]++,du[y]++;
	}
	deep[0]=-1;
	dfs1(s,0);
	dfs2(s);
	printf("%d
",ans);
	return 0;
}