萌新10pts求条
查看原帖
萌新10pts求条
752094
MornHus楼主2023/10/28 18:10
#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
vector<int>g[maxn];
int n;
int dp[maxn][3];
void dfs(int now,int fa){
	if(g[now].size()==1&&g[now][0]==fa){
		dp[now][0]=1;
		dp[now][2]=1;
		dp[now][1]=0x3f3f3f3f;
		return ;
	}
	int greatest=0x3f3f3f3f,tar=0;
	
	for(int i=g[now].size()-1;i>=0;i--){
		int to=g[now][i];
		if(to==fa)continue;
		dfs(to,now);
		
		dp[now][0]+=min({dp[to][0],dp[to][1],dp[to][2]});
		
		dp[now][2]+=min(dp[to][0],dp[to][1]);
		
		if(dp[to][0]<greatest){
			greatest=dp[to][0];
			tar=to;
		}
	}
	
	for(int i=g[now].size()-1;i>=0;i--){
		int to=g[now][i];
		if(to==fa||to==tar)continue;
		dp[now][1]+=min(dp[to][0],dp[to][1]);
	}
	dp[now][1]+=greatest;
	return ;
}
int main(){
	cin>>n;
	for(int i=1,a,b;i<n;i++){
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1,0);
	cout<<min(dp[1][0],dp[1][1]);
	return 0;
} 

/*
dp状态设计:

dp[i][j] 以i为根节点的子树中,j状态:{0自己覆盖,1儿子覆盖,2父亲覆盖}

所需的最少

dp[i][0]+=min(dp[son][1],dp[son][2],dp[son][0]);

dp[i][2]+=min(dp[son][0],dp[son][1]);

dp[i][1]=dp[greatest_son][0]+sigma(min (dp[son][0],dp[son][1])); 


*/
2023/10/28 18:10
加载中...