P4186 [USACO18JAN] Cow at Large G题解
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;
}