Algorithm/problem
백준 2533 : 사회망 서비스(SNS) - 트리 DP, C++
DingCoDing
2022. 10. 3. 20:27
반응형
https://www.acmicpc.net/problem/2533
#include <bits/stdc++.h>
using namespace std;
#define MX 1000001
int N, dp[MX][2];
vector<int> adj[MX];
bool vis[MX];
void DFS(int node){
vis[node] = 1;
dp[node][0] = 1;
for(auto nx : adj[node]){
if(vis[nx]) continue;
DFS(nx);
dp[node][0] += min(dp[nx][0], dp[nx][1]);
dp[node][1] += dp[nx][0];
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N;
for(int i=0; i<N-1; i++){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
DFS(1);
cout << min(dp[1][0], dp[1][1]) << '\n';
return 0;
}
반응형