문제
풀이
DFS와 DP를 이용한 문제이다. Reference를 참조하였다. dp[index][2]를 선언하여 dp[index][0]은 index번째 정점이 포함이 된 경우. dp[index][1]은 index번째 정점이 포한된 경우를 의미한다. 계속해서 dfs로 function call을 하고, dp[now]0는 그 전 자식노드를 포함해도 되고, 그 전 자식노드를 포함하지 않아도 된다. 두 개를 비교하여 큰 값으로 입력하도록 한다. dp[now][1]의 경우, 그 자식 노드는 포함되지 않아야하므로, dp[map[now][i][0]을 덧셈하도록 한다. 그 이후 root인 1번이 포함된 경우와 포함되지 않은 경우 중 큰 값을 출력하도록 하면 최대 독립 집합 가중치 값을 알 수 있다. trace는 해당 노드가 포함된다면, 그 노드를 정답 벡터에 포함시키고 그 자식 노드는 포함안되는 것을 funciton call 하게 한다. 해당 노드가 포함되지 않는다면 자식노드를 포함한 경우와 포함하지 않은 경우의 dp값을 비교하여 큰 경우 자식노드를 포함한 것으로 function call, 그렇지 않다면 자식노드를 포함하지 않은 것으로 function call하여 진행한다. 그 이후 정답 벡터를 sort를 하여 정답을 출력한다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int vertex[10001];
vector<int> map[10001];
int dp[10001][2];
vector<int> res;
void dpdfs(int now, int parent){
for(int i = 0; i<map[now].size(); i++){
if(map[now][i] == parent) continue;
else{
dpdfs(map[now][i], now);
}
}
dp[now][0] = 0;
dp[now][1] = vertex[now];
for(int i = 0; i<map[now].size(); i++){
if(map[now][i] == parent) continue;
dp[now][0] += max(dp[map[now][i]][0], dp[map[now][i]][1]);
dp[now][1] += dp[map[now][i]][0];
}
}
void trace(int now, int isinclude, int parent){
if(isinclude == 1){
res.push_back(now);
for(int i = 0; i<map[now].size(); i++){
if(map[now][i] == parent) continue;
trace(map[now][i], 0, now);
}
}
else{
for(int i = 0; i<map[now].size(); i++){
if(map[now][i] == parent) continue;
if(dp[map[now][i]][0] < dp[map[now][i]][1]){
trace(map[now][i], 1, now);
}
else trace(map[now][i], 0, now);
}
}
}
int main(){
int N;
scanf("%d", &N);
for(int i = 1; i<=N; i++){
scanf("%d", &vertex[i]);
}
for(int i = 0; i<N-1; i++){
int from, to;
scanf("%d %d", &from, &to);
map[from].push_back(to);
map[to].push_back(from);
}
dpdfs(1, 0);
printf("%d\n", max(dp[1][0], dp[1][1]));
if(dp[1][1] > dp[1][0]){
trace(1, 1, 0);
}
else trace(1, 0, 0);
sort(res.begin(), res.end());
for(int i = 0; i<res.size(); i++){
printf("%d ", res[i]);
}
}
