本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-08 19:01:57

Link

贪心神仙题。

注意「割」字眼在文中的实际意义并非割点/割边，而是割集

考虑把在放满人情况下，人只往上走，Bessie 只往下走情况下，人抓到 Bessie 的点/边称为相遇点/边，选择其中所有 没有祖宗是相遇点/边 的相遇点/边，作为根到叶子的割集。（这里不需要纠结边和点在割中的区别，可以看作在每条边中间都放了一个中间点来将边转化为点，以下直接简称为相遇点）

那么我们会发现答案就是割的大小。

考虑证明。

首先其一定存在，这个显然。

割集内的每一个点都可以不唯一但不重复的对应到一个叶子，这里不唯一是没有关系的，不重复是较重要的。这意味着我们可以用割来对应题目的解——选择的叶子集合。以下对于答案的讨论都是对于割集的。选择割集所对应的叶子集合是一定合法的。

接下来考虑是否最优。

将一个人的路径是所在叶子到根的唯一路径，因为反过来追是一定追不上的。

非相遇点是无用的，因为这些点要么是人在不错过 Bessie 时到达不了的点（割上面的点），要么是可以被割中点所替代的（割下面的点）。

在割下面（更靠近叶子）的相遇点是无用的，可以被割中点替代。

根据选取规则，割上面没有相遇点。

所以由割集得出的答案叶子集合是一个存在，合法且最优的答案集合。

（感觉证得好混乱，但感性理解是非常容易的）

代码实现则非常简单，只需要预处理一下每一棵子树的最浅叶子到自身距离，求解则直接 dfs 找割即可。

code

const int N=2e5+5;

struct edge{
	int v,nxt;
}e[N<<1];
int head[N],tott;
int in[N];
void add(int u,int v){e[++tott]={v,head[u]},head[u]=tott;in[u]++;}

int len[N];
void dfs(int u,int faa){
	len[u]=in[u]==1?0:inf;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==faa)
			continue;
		dfs(v,u);
		len[u]=min(len[u],len[v]+1);
	}
}

int cnt;
void calc(int u,int faa,int dep){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==faa)
			continue;
		if(len[v]<=dep+1)\/\/儿子是割点\/到儿子的边是割边
			cnt++;
		else
			calc(v,u,dep+1);
	}
}

signed main(){
	int n=read(),k=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	dfs(k,0);
	calc(k,0,0);
	print(cnt),pc('\n');
	return 0;
}