백준 2533 : 사회망 서비스(SNS) - 트리 DP, C++

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

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

#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;
}