풀이
이 문제는 2번과 3번 규칙에 유의해야한다. 2번 규칙에서 어느 한 마을이 우수마을로 선정되면 주변 마을은 모두 우수마을이 될 수 없다. 하지만,
우수마을이 아닌 마을들 끼리는 인접할 수 있다. 무슨 말이냐면 무조건 우수 - 우수아님 - 우수 - 우수아님이럴 필요가 없다는 말이다. 예를 들어 이런 것도 가능하다.
우수-우수아님-우수아님 -우수
4번 마을이 3번 마을보다 인구수가 많으면 밑에 것이 채택되어야 할것이다.
나는 이 문제에 접근 할때 dp[2][N+1]짜리 배열을 만들었다. 그리고
dp[0][i]에는 i번째 마을이 우수마을이 아닌 상황에서의 인구수를 넣었다.
dp[1][i]에는 i번째 마을이 우수마을인 상황에서의 인구수를 넣었다.
그리고 나는 1번 마을을 트리의 루트로 두고 DFS를 사용하여 리프노드까지 간다음 거기서 DP를 사용하였다.
1,2,3이 4번 마을의 child라고 하자. 그럼 여기서 두가지 상황이 있다.
1,2,3이 모두 우수마을이고 4는 우수마을이 아니다. 그리고 그 반대이다.
첫번째 경우 dp[0][4]에 dp[1][1~3]이 더한 값이 들어가게 된다.
두번째 경우 dp[1][4]에 4번 노드의 인구수가 더해지고 dp[0][1~3]이 더해지게 된다. 그리고 dp[1][1~3]에는 1~3이 리프노드이므로 1~3번 노드의 인구수가 각각 들어가게 된다. dp[0][1~3]은 그냥 0이다.
이 때 이런 의문이 생긴다. 추가로 5,6,7,8,9번 마을이 있다고 하자. 5,6,7은 리프노드이며 8번 노드의 자식들이다. 그리고 4,8은 9번 노드의 자식들이라고 하자. 이 때 9번 노드의 상황을 한번 살펴보자
9번 노드에게는 여러 상황이 있을 수 있는데 규칙 중 3번 규칙을 위배하는 경우를 생각해보자. 간단하다. 1,2,3번 노드가 우수 마을이고 4가 우수 마을이 아니다. 마찬가지로 리프노드인 5,6,7이 우수 마을이고 8은 우수마을이 아니다. 각각이 일단은 4,8이 루트인 서브 트리에선 인구수 최대라고 하자. 그럼 일단 9번 노드의 자식들은 모두 우수마을이 아니다. 이때 이런 상황이 발생한다. 9번 노드가 우수마을이 아닐 때 9번 노드는 우수 마을에 인접해있지 않을 수 있는 상황이 발생한다. dp[0][9]는 dp[0][4] + dp[0][8]이다. 그리고 만약 9번노드의 parent인 11번 노드가 있는데 이 11번 노드가 10번노드를 child로 가지고 있다고 해보자. 그리고 이 10번노드가 엄청나게 큰 인구수를 가지고 있어 10번이 우수마을이 되었다고 하자 그럼 11번 노드는 무조건 우수마을이 될 수 없다. 이렇게 되면 9번은 인접해있는 4,8,11이 모두 우수마을이 아니게 된다. 그럼 9번이 우수마을이 되면 된다. 자동으로 되게 할 수 있다. 왜냐하면 이런 상황에서는 dp[0][9]보다 dp[1][9]이 딱 9번 노드의 인구수만큼 차이나게 된다. 이것을 다음과 같이 해결 할 수 있다. 11번 노드에서 child 노드를 순환할 때 9번 10번이 존재한다. 10은 1이므로 11은 0이 되어야 한다. 그리고 9번 노드를 확인할 때 max(dp[0][9], dp[1][9])를 통해 9번노드에서의 정보를 가져오는데 이경우 dp[1][9]가 무조건 뽑히게 되며 자동으로 9번노드가 우수마을이 된다.
다음은 전체 코드이다.
#include<iostream>
#include<vector>
using namespace std;
int N;
void DFS(vector<vector<int>> &adj, vector<vector<int>> &dp, vector<int>& people, int parent, int cur) {
if ( adj[cur].size() == 1 && parent == adj[cur][0] ) {
dp[0][cur] = 0;
dp[1][cur] = people[cur];
return;
}
dp[1][cur] += people[cur];
for ( int child : adj[cur] ) {
if ( child == parent )continue;
DFS(adj, dp, people, cur, child);
dp[0][cur] += max(dp[0][child], dp[1][child]);
dp[1][cur] += dp[0][child];
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
cin >> N;
vector<int> people(N + 1);
vector<vector<int>> adj(N + 1, vector<int>());
vector<vector<int>> dp(2, vector<int>(N+1,0));
for ( int i = 1; i < N + 1; i++ ) {
cin >> people[i];
}
for ( int i = 0; i < N - 1; i++ ) {
int t1, t2;
cin >> t1 >> t2;
adj[t1].emplace_back(t2);
adj[t2].emplace_back(t1);
}
DFS(adj, dp, people, 0, 1);
cout << max(dp[0][1], dp[1][1]) << endl;
return 0;
}