BOJ)2213 트리의 독립집합

문제: icpc.me/2213

트리에서 각 정점에 대한 가중치가 주어지고 정점들의 가중치를 최대로 가지는 최대독립집합 set을 구하는 문제이다.

트리에서의 최대 독립집합을 구하는 문제이기 때문에 사이클이 존재하지 않으므로 다이나믹 프로그래밍으로 해결할 수 있다.

dp[pos][state]로 pos번째 정점에 대한 선택여부를 state로 강제한다면 점화식을 쉽게 세워줄 수 있다.

해당 정점을 선택할 경우 해당 정점에 대한 가중치를 얻고 자식들은 state를 선택안함으로 강제된다.

해당 정점을 선택하지 않을 경우 자식들의 state 결과는 선택하거나 선택안하는 경우 중 최댓값을 가지게 된다.

두 케이스에 따라 점화식을 다르게 세워준 후 다이나믹 프로그래밍을 이용하여 답을 구해준 뒤 역추적을 해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
vector<vector<int>> vt, chd;
int n, g[10001], dp[10001][2], x, y, visited[10001];
pair<int, int> back[10001][2];
vector<int> r;
void dfs(int here, int par) {
    visited[here] = 1;
    if (here != 1)chd[par].push_back(here);
    for (auto next : vt[here]) {
        if (!visited[next])
            dfs(next, here);
    }
}
int func(int pos, int state) {
    int &ret = dp[pos][state];
    if (ret != -1)return ret;
    ret = 0;
    if (state) {
        ret = g[pos];
        for (auto next : chd[pos])
            ret += func(next, 0);
    }
    else {
        for (auto next : chd[pos])
            ret += max(func(next, 1), func(next, 0));
    }
    return ret;
}
void ff(int pos, int state) {
    if (state) {
        r.push_back(pos);
        for (auto next : chd[pos])
            ff(next, 0);
    }
    else {
        for (auto next : chd[pos]) {
            if (dp[next][1] >= dp[next][0])
                ff(next, 1);
            else
                ff(next, 0);
        }
    }
}
int main() {
    scanf("%d", &n);
    vt.resize(n + 1);
    chd.resize(n + 1);
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= n; i++)
        scanf("%d", &g[i]);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d", &x, &y);
        vt[x].push_back(y);
        vt[y].push_back(x);
    }
    dfs(1, 0);
    int x = func(1, 0);
    int y = func(1, 1);
    if (x >= y)
        ff(1, 0);
    else
        ff(1, 1);
    printf("%d\n", max(x, y));
    sort(r.begin(), r.end());
    for (auto h : r)
        printf("%d ", h);
    return 0;
}