BOJ 2213 트리의 독립집합

1 개요

BOJ 2213 트리의 독립집합

• 백준 온라인 저지 2213번 문제
• BOJ 38단계

2 C++

#include <bits/stdc++.h>
using namespace std;
 
int n;
int w[10001];
int dp[10001][2];
bool visited[10001];
vector<int> tree[10001];
vector<int> path;
 
void dfs(int cur) {
    dp[cur][0] = 0;
    dp[cur][1] = w[cur];
    visited[cur] = true;
    for(int i = 0; i < tree[cur].size(); i++) {
        int next = tree[cur][i];
        if(visited[next]) continue;
        dfs(next);
        dp[cur][0] += max(dp[next][0], dp[next][1]);
        dp[cur][1] += dp[next][0];
    }
}
 
void trace(int cur, int prev) {
    if(dp[cur][1] > dp[cur][0] && !visited[prev]) {
        path.push_back(cur);
        visited[cur] = true;
    }
    for(int i = 0; i < tree[cur].size(); i++) {
        int next = tree[cur][i];
        if(next == prev) continue;
        trace(next, cur);
    }
}
 
void solve() {
    dfs(1);
    memset(visited, 0, sizeof(visited));
    trace(1, 0);
    sort(path.begin(), path.end());
    cout << max(dp[1][0], dp[1][1]) << '\n';
    for (auto &w : path) {
        cout << w << ' ';
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> w[i];
    }
    int a, b;
    for(int i=1; i<n; i++){
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    solve();
}