50pts求调,#6-#10WA
查看原帖
50pts求调,#6-#10WA
1652696
Summer_river楼主2025/1/23 23:23
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100010
using namespace std;
inline long long read()
{
	long  long x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
vector<int>e[N];
int f[N][3],g[N],n;
void dfs(int u,int fa)
{
	memset(g,0,sizeof(g));
	f[u][0]=1;
	int tot=0;
	for(int v:e[u])
	{
		if(v==fa) continue;
		dfs(v,u);
		f[u][0]+=min(min(f[v][0],f[v][1]),f[v][2]);
		f[u][2]+=min(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
		g[++tot]=f[v][1]-f[v][0];
	}
	if(!tot)
	{
		f[u][1]=1e9;
		return;
	}
	sort(g+1,g+tot+1);
	for(int i=1;i<tot;i++)
	{
		if(g[i]>=0) break;
		else f[u][1]+=g[i];
	}
}
int main(){
	n=read();
	for(int i=1;i<n;i++){
		int x,y;
		x=read();y=read();
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
	printf("%d",min(f[1][1],f[1][0]));
	return 0;
}
2025/1/23 23:23
加载中...