[BOJ] 2213 트리의 독립집합

(2021년 1월 13일에 작성한 글입니다.)

2213번: 트리의 독립집합

우수마을 문제(1949번)랑 비슷하다

차이점이 있다면 독립집합을 찾아줘야 한다는 거.

​

경찰차 문제(2618번)에서 처럼

dp값이 채워지는 경로를 찾아 가면 된다.

함수 print(int cur, bool flag)를 만들었고

cur 변수는 현재 확인중인 노드 번호,

flag는 이 노드가 독립집합에 속해 있는 친구인지를 저장해줬다.

​

현재 노드를 독립집합에 포함시킨 상태라면 (flag == true라면)

ans 벡터에 cur 값을 넣어주고

인접 노드들은 모두 독립집합에 포함되지 않아야 하기 때문에

인접 노드들에 대해 print(next, false)를 부른다.

​

그리고 만약 현재 노드가 독립집합에 포함되어 있지 않다면(flag == false라면)

인접 노드에 대해서는 포함/불포함 중 큰 값을 더했으니까

만약 인접 노드를 포함하는 게 이득이라면, 인접 노드를 포함했다고 표시해 함수를 부르고 (print(next, true))

포함하지 않는 게 이득이라면, 인접 노드를 포함하지 않았다고 표시해 함수를 부름(print(next, false))

​

그리고 출력하기 전에 ans 벡터 정렬해주고 출력하면 된다

vector<int> w;
vector<vector<int>> adj;
vector<vector<int>> dp;
vector<bool> chk;
vector<int> ans;

void solve(int);
void getAns(int cur, bool flag);

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	int i;
	
	cin >> N;
	w.resize(N + 5);
	for (i = 1; i <= N; i++) {
		cin >> w[i];
	}
	adj.resize(N + 5);
	for (i = 0; i < N - 1; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	dp.resize(2, vector<int> (N + 5, -1));
	chk.resize(N + 5, false);
	chk[1] = true;
	solve(1);

	cout << max(dp[0][1], dp[1][1]) << ENDL;

	chk.clear(); chk.resize(N + 5, false);
	chk[1] = true;
	dp[0][1] > dp[1][1] ? getAns(1, false) : getAns(1, true);

	sort(ans.begin(), ans.end());
	for (int n : ans) {
		cout << n << ' ';
	}
	cout << ENDL;

	return 0;
}

void solve(int cur)
{
	if (dp[0][cur] != -1) {
		return;
	}

	dp[0][cur] = dp[1][cur] = 0;
	for (int next : adj[cur]) {
		if (chk[next]) {
			continue;
		}

		chk[next] = true;
		solve(next);
		dp[0][cur] += max(dp[0][next], dp[1][next]);
		dp[1][cur] += dp[0][next];
	}
	dp[1][cur] += w[cur];
}

void getAns(int cur, bool flag)
{
	if (flag) {
		ans.push_back(cur);
		for (int next : adj[cur]) {
			if (chk[next]) {
				continue;
			}
			chk[next] = true;
			getAns(next, false);
		}
	}
	else {
		for (int next : adj[cur]) {
			if (chk[next]) {
				continue;
			}
			chk[next] = true;
			dp[0][next] > dp[1][next] ? getAns(next, false) : getAns(next, true);
		}
	}
}