分析
对于 \(A\) 来说，最坏情况即 \(B\) 一路走到他最不好拦下的叶子结点，因为 \(B\) 不可能往回走，否则就浪费了，任 \(A\) 宰割。
对于每一个节点来说， \(A\) 需要确保两个事情，一个是保住它的所有子节点，二是用剩余的力量去提前处理它的后代们的问题。易得这是一个树形 \(DP\) ，而我们可以二分列举 \(A\) 的力量，然后用它去解决问题，判断是否能处理。
对于 \(dp\) 的转移式，我们通过上述分析可以得出对于某个节点，它对祖先们只有需要分担和不需要两种状态，不会去帮祖先分担，因此 \(dp\) 值要么为0，要么为它需要祖先帮忙分担的力量。
因此，我们可以得到核心转移式。
sum+=f[v]+1;
f[u]=max(0,sum-mid);
有了这个，最后只要得到 \(f_1=0\) ，即根节点有该条件就能完美地处理所有节点的问题，不需要某个神秘力量在帮根节点分担，说明 \(mid\) 可行，存入 \(ans\) 并更新 \(right\) ，查找更小答案，否则更新 \(left\) ，不断缩短，得出答案。
代码
#include<bits/stdc++.h>
using namespace std;
int n,f[300001],le,ri,mid,ans,head[300001],tot;
struct node{//邻接表
int to,next;
}a[600001];
void check(int u,int fr,int k){//深搜
int sum=0;
for(int i=head[u];i;i=a[i].next){
int v=a[i].to;
if(v==fr)continue;//判断父节点
check(v,u,k);
sum+=f[v]+1;//染色子节点，并帮忙分担
}
f[u]=max(0,sum-k);//如果能力超出需要，只说明不需要祖先帮忙分担，无法做出更多贡献
}
void read(int &res){
res=0;
char c=getchar();
while(c<‘0‘||c>‘9‘)c=getchar();
while(c>=‘0‘&&c<=‘9‘){res=(res<<1)+(res<<3)+c-48;c=getchar();}
}
void add(int q,int m){
a[++tot].to=m;
a[tot].next=head[q];
head[q]=tot;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n;
for(int i=1;i<n;i++){
int x,y;
read(x);read(y);
add(x,y);
add(y,x);
}
le=0;ri=n;
while(le<=ri){
int mid=(le+ri)>>1;
check(1,0,mid);
if(f[1]==0){//可行，更新答案
ans=mid;
ri=mid-1;
}
else le=mid+1;
}
cout<<ans<<endl;
return 0;
}