二分答案
第二个人不会走回头路
那么F[i]表示在i的子树内(不包括i)所需要的额外步数
F[1]==0表示mid可行
k可能为0
#include<cstdio>
#include<algorithm>
using namespace std;
int cnt,n,mid,F[300005],last[300005];
struct node{int to,next;
}e[600005];
void add(int a,int b){e[++cnt].to=b;e[cnt].next=last[a];last[a]=cnt;
}
void dfs(int x,int fa){F[x]=0;for (int i=last[x]; i; i=e[i].next){int V=e[i].to;if (V==fa) continue;dfs(V,x);F[x]+=F[V]+1; }F[x]=max(F[x]-mid,0);
}
int main(){scanf("%d",&n);for (int i=1; i<n; i++){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}int l=0,r=n;while (l<r){mid=(l+r)>>1;dfs(1,0);if (!F[1]) r=mid;else l=mid+1;}printf("%d\n",l);return 0;
}
