40pts求调
查看原帖
40pts求调
1077850
gaohaoyuan楼主2025/2/8 17:46
#include<stdio.h>
#include<algorithm>
#include<unordered_map>
#define man 100005
#define r
enum STATE
{
	self=0,
	son=1,
	father=2,
};
using std::min;
std::unordered_map<STATE,int> f[man];
int n,g[man],cnt,next[man],to[man],head[man];
void add(int x,int y)
{
    to[++cnt]=y;
    next[cnt]=head[x];
    head[x]=cnt;
}
void dfs(int u,int fa)
{
	int tot=0;
	f[u][self]=1;
	for(int i=head[u];i!=self;i=next[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs(v,u);
		f[u][self]+=min(f[v][self],min(f[v][son],f[v][father]));
		f[u][son]+=f[v][self];
		f[u][father]+=min(f[v][self],f[v][son]);
		g[++tot]=f[v][son]-f[v][self];
	}
r	if(tot==self) f[u][son]=__INT32_MAX__;//u没有儿子
	else//u有儿子
	{	
		std::sort(g+1,g+tot+1);
		for(int i=1;i<tot;i++)
		{
			if(g[i]<0) f[u][son]+=g[i];
			else break;
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
    dfs(1,0);
    printf("%d",std::min(f[1][self],f[1][son]));
	return 0;
}
2025/2/8 17:46
加载中...