2533

https://www.acmicpc.net/problem/2533

2533번: 사회망 서비스(SNS)

 

1. 부모가 얼리어댑터가 아닐 때 : dp[부모][0] += dp[자식][1]

2. 부모가 얼리어댑터일 때 : dp[부모][1] += min(dp[자식][0],dp[자식][1])

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
int N;
int dp[1000010][2];
vector<int> v[1000010];
void dfs(int x,int par){
    if(dp[x][0] != -1) return;
     dp[x][0] = 0;
     dp[x][1] = 1; 
	for(int i:v[x]){
	if(i==par) continue;
	    dfs(i,x);
		dp[x][0] += dp[i][1]; 
        dp[x][1] += min(dp[i][1],dp[i][0]);  
}
   return ;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i=0,u,x;i<N -1;i++){
		cin>>u>>x;
		v[u].push_back(x);
		v[x].push_back(u);
	}
	memset(dp,-1,sizeof(dp));
	v[0].push_back(1);
	dfs(1,0);
//	for(int i =0 ; i <= N ;i++) cout<<dp[i][0]<<" "<<dp[i][1]<<'\n';
	cout<<min(dp[1][0],dp[1][1]);	
	return 0;
}