二分答案

第二个人不会走回头路

那么F[i]表示在i的子树内(不包括i)所需要的额外步数

F[1]==0表示mid可行

k可能为0

#include
     
      #include
      
       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
       
        >1;		dfs(1,0);		if (!F[1]) r=mid;		else l=mid+1;	}	printf("%d\n",l);	return 0;}