标签：return cf1739D int 200100 scanf mid ans

题意

每次可以选择树上的一条边fa，u，将此边断开，连到根1上面

询问k次操作后，一棵树的最小深度

想法

初见，第一反应直接贪心取最深的那一条路上的中间边

经过几组思考，发现答案具有二分性质，枚举最小深度，自底向上，如果超过最小深度，则强行截断

#include<bits/stdc++.h>
using namespace std;
int n,k;
int inv[200100],fa[200100],deep[200100],que[200100],tmp[200100];
bool solve(int key)
{
	int l(1),r(0),num(0);
	for (int i=1;i<=n;i++)
	{
		if (inv[i]==0) r++,que[r]=i;
		tmp[i]=inv[i];
		deep[i]=1;
	}
	while (l<=r)
	{
		int u=que[l]; 
		l++;
		if (deep[u]==key&&fa[u]!=1) num++,tmp[fa[u]]--;
		else
		{
			deep[fa[u]]=max(deep[fa[u]],deep[u]+1);
			tmp[fa[u]]--;
		}
		if (tmp[fa[u]]==0) r++,que[r]=fa[u];
		//if (n==5&&k==2) printf("QQ%d %d\n",u,num);
		if (num>k) return 0;
	}
	return 1;
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d%d",&n,&k);
		for (int i=1;i<=n;i++) inv[i]=0;
		for (int i=2;i<=n;i++) 
		{
			scanf("%d",&fa[i]);
			inv[fa[i]]++;	
		}
		fa[1]=1;
		//for (int i=1;i<=n;i++) printf("%d ",inv[i]);
		//printf("\n");
		int l(1),r(n-1),ans(n-1);
		while (l<=r)
		{
			int mid=(l+r)>>1;
			//printf("%d\n",mid);
			if (solve(mid)==1) ans=mid,r=mid-1;
			else l=mid+1;
		}
		printf("%d\n",ans);
	}
	return 0;
} 

标签：return,cf1739D,int,200100,scanf,mid,ans
From： https://www.cnblogs.com/by-w/p/16747676.html