70分求助
查看原帖
70分求助
590609
jiangjiangQwQ楼主2023/8/7 11:16
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int N=5e5+5;
#define For(i,l,r) for(register int i=l;i<=r;i++)
#define int __int128
inline void read(int &x){
	   x=0;int f=1;
	   char c=getchar();
	   while(!isdigit(c)){
			if(c=='-') f=-1;
			c=getchar();
	   }while(isdigit(c)){
			x=x*10+c-'0';
			c=getchar();
	   }x*=f;
}
inline void write(int x){
	   if(x<0){x=-x;putchar('-');}
	   if(x>9) write(x/10);
	   putchar(x%10+'0');
}int n,x,y;
vector<int> edge[N];
int f[N][3];
/*
f[u][0]被himself覆盖 f[u][0]+=min{f[v][1],f[v][0],f[v][2]} 
f[u][1]被son覆盖 f[u][1]=f[x][0]+sigma{min{f[v][0],f[v][1]}}
f[u][2]被fa覆盖 f[u][2]+=min{f[v][0],f[v][1]} 
*/
inline void dfs(int u,int fa){
	f[u][0]=1;f[u][1]=1e18;
	int Min0=1e18,sum=0,id=0;
	for(int j=0;j<edge[u].size();j++){
		int v=edge[u][j];
		if(v!=fa){
			dfs(v,u);
			f[u][0]+=min(min(f[v][0],f[v][1]),f[v][2]);
			if(f[v][0]<Min0){
				Min0=f[v][0];
				id=v;
			}f[u][2]+=min(f[v][0],f[v][1]);
		}
	}for(int j=0;j<edge[u].size();j++){
		int v=edge[u][j];
		if(v!=fa&&v!=id){
			sum+=min(f[v][0],f[v][1]);
		}
	}f[u][1]=Min0+sum;
}int indgr[N];
signed main(){
	read(n);
	for(int i=1;i<=n-1;i++){
		read(x);read(y);
		edge[x].push_back(y);
		edge[y].push_back(x);
		indgr[y]++;
	}
	int start=0;
	for(int i=1;i<=n;i++){
		if(!indgr[i]){
			start=i;
			dfs(start,0);
			write(min(f[start][0],f[start][1]));
			exit(0);
		}
	}
	return 0;
}
2023/8/7 11:16
加载中...