bzoj 2067: [Poi2004]SZN【贪心+二分+树形dp】

第一问就是Σ(deg[u]-1)/2+1

第二问是二分，判断的时候考虑第一问的贪心规则，对于奇度数的点，两两配对之后一条延伸到上面；对于欧度数的点，两两配对或者deg[u]-2的点配对，然后一条断在这个点，一条延伸上去，按这个树形dp判断一下即可

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=10005;

int n,h[N],cnt,ans=1,d[N],f[N],fl,a[N],tot;

struct qwe

{

	int ne,to;

}e[N<<1];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	d[v]++;

	h[u]=cnt;

}

bool pd(int mid,int w)

{

	int l=1,r=tot;

	while(l<r)

	{

		if(l==mid)

			l++;

		if(r==mid)

			r--;

		if(a[l]+a[r]>w)

			return 0;

		l++,r--;

	}

	return 1;

}

void dfs(int u,int fa,int w)

{

	if(!fl)

		return;

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].to!=fa)

			dfs(e[i].to,u,w);

	f[u]=0,tot=0;

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].to!=fa)

			a[++tot]=f[e[i].to]+1;

	sort(a+1,a+1+tot);

	if(!tot)

		return;

	if(a[tot]>w)

	{

		fl=0;

		return;

	}

	if(!(tot&1))

	{

		for(int i=1;i<=tot/2;i++)

			if(a[i]+a[tot-i+1]>w)

			{

				if(u==1)

				{

					fl=0;

					return;

				}

				else

				{

					tot--;

					break;

				}

			}

	}

	if(tot&1)

	{

		int l=1,r=tot,ans=tot+1;

		while(l<=r)

		{

			int mid=(l+r)>>1;

			if(pd(mid,w))

				r=mid-1,ans=mid;

			else

				l=mid+1;

		}

		if(ans>tot)

		{

			fl=0;

			return;

		}

		else

			f[u]=a[ans];

	}

}

bool ok(int w)

{

	fl=1;

	dfs(1,0,w);

	return fl;

}

int main()

{

	n=read();

	for(int i=1;i<n;i++)

	{

		int x=read(),y=read();

		add(x,y),add(y,x);

	}

	for(int i=1;i<=n;i++)

		ans+=(d[i]-1)>>1;

	int l=1,r=n,len=1;

	while(l<=r)

	{

		int mid=(l+r)>>1;

		if(ok(mid))

			r=mid-1,len=mid;

		else

			l=mid+1;

	}

	printf("%d %d\n",ans,len);

	return 0;

}

巴特西

bzoj 2067: [Poi2004]SZN【贪心+二分+树形dp】

最新文章

热门文章