트리 dp 문제 모음

2533 사회망서비스

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

 

트리 위에서 자신 또는 자신과 연결된 모든 노드 중에서 색칠된 노드가 한개라도 존재하도록 노드를 색칠해야 하는 최소 개수를 구하는 문제이다.

리프노드까지 내려가서 자신과 부모 모두 칠해지지 않은 경우에만 더 많은 노드를 커버할 수 있는 부모노드를 색칠하는 방법으로 해결할 수 있다.(약간 그리디 느낌?) 

#include <iostream>
#include <vector>
#define Max 1000001
using namespace std;

vector<vector<int>> connected(Max);
vector<vector<int>> children(Max);
int dp[Max], parent[Max], N, root;
bool colored[Max];

void make_tree(int curr, int p) {
    for(int c : connected[curr]) {
        if(c != p) {
            parent[c] = curr;
            children[curr].push_back(c);
            make_tree(c, curr);
        }
    }
}

void sns(int curr) {
    for(int c : children[curr]) {
        sns(c);
        dp[curr] += dp[c];
    }
    if(curr == root)
        return;

    if(!colored[parent[curr]] && !colored[curr]) {
        dp[curr] += 1;
        colored[parent[curr]] = true;
    }
}

int main(){

    cin >> N;

    for(int i = 0; i < N-1; i++) {
        int u, v;
        cin >> u >> v;
        connected[u].push_back(v);
        connected[v].push_back(u);
    }

    root = 1;
    make_tree(root, -1);
    sns(root);

    cout << dp[root];
}

 

 

 

2213 트리의 독립집합

http://acmicpc.net/problem/2213

 

 

각 노드에 가중치가 존재할 때, 가중치합을 최대화하는 트리의 독립집합의 크기를 구하고, 이를 구성하는 노드도 구해야 하는 문제이다.

현재 노드를 고르는지, 고르지 않는지에 따라서 리프노드에서부터 dp값을 하나씩 채워나가면 되는 문제이다.

역추적 또한, 루트노드에서 시작해서 부모노드가 선택되었는지에 따라 노드를 선택할 지 판별해주면 된다.

 

#include <bits/stdc++.h>
#define MAX 10001
using namespace std;
vector<int> w(MAX), parent(MAX), ans;
vector<vector<int>> connected(MAX), dp(MAX, vector<int>(2, 0)), children(MAX);
void make_tree(int node, int p) {
	for(int c : connected[node]) {
		if(c == p)continue;
		children[node].push_back(c);
		parent[c] = node;
		make_tree(c, node);
	}
}
void max_sum(int curr) {
	dp[curr][0] = 0;
	dp[curr][1] = w[curr];
	for(int c : children[curr]) {
		max_sum(c);
		dp[curr][0] += max(dp[c][0], dp[c][1]);
		dp[curr][1] += dp[c][0];
	}
}
void bt(int curr, bool parent_selected) {
	if(!parent_selected) {
		if(dp[curr][1] > dp[curr][0]) {
			ans.push_back(curr);
			for(int c : children[curr]) {
				bt(c, true);
			}
		}
		else {
			for(int c : children[curr]) {
				bt(c, false);
			}
		}
	}
	else {
		for(int c : children[curr]) {
			bt(c, false);
		}
	}
}
int main() {
	int N;
	cin >> N;
	for(int i = 1; i <= N; i++) {
		cin >> w[i];
	}
	for(int i= 0; i < N-1; i++) {
		int u, v;
		cin >> u >> v;
		connected[u].push_back(v);
		connected[v].push_back(u);
	}
	make_tree(1, -1);
	max_sum(1);
	bt(1, false);
	cout << max(dp[1][0], dp[1][1]) << "\n";
	sort(ans.begin(), ans.end());
	for(int x : ans) {
		cout << x << " ";
	}
}