[백준] 1949번 우수마을

1949 우수마을

풀이)

백준 2533번 사회망서비스 문제랑 똑같이 dp를 사용해서 풀면 된다.

사회망 문제 설명) https://comyoung.tistory.com/41

+)트리는 사이클이 없는 무방향 그래프이므로 어느 정점에서 시작하든 상관없다.

   나같은 경우는 1번 마을을 트리의 root라고 생각하고 시작해줬다.

주의사항

처음에 트리 구현할 때

무조건 번호 작은 노드가 번호가 큰 노드의 부모이게 만들어, 양방향으로 마을을 연결되지 않게 했었다.

이렇게 풀면 트리가 제대로 구현되지 않아 틀리게 된다.

반례) 1-3, 2-3

코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
int arr[10001];
vector <int> adj[10001];
int dp[10001][2];
bool visited[10001];
 
void cal(int node) {
    dp[node][0] = 0;
    dp[node][1] = arr[node];
    for (int i = 0; i < adj[node].size(); i++) {
         int next = adj[node][i];
        if (!visited[next]) {
            visited[next] = true;
            cal(next);
            //내가 우수마을이 아니라면 -> 내 이웃은 우수거나 우수 아님
            dp[node][0] += max(dp[next][1], dp[next][0]);
            //내가 우수마을이라면 -> 내 이웃은 우수 아님
            dp[node][1] += dp[next][0];
        }
        
    }
}
int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) scanf("%d", &arr[i]);
    int v1, v2;
    for (int i = 1; i <= N - 1; i++) {
        scanf("%d %d", &v1, &v2); 
        adj[v1].push_back(v2); 
        adj[v2].push_back(v1);
    }
    visited[1] = true;
    cal(1);
    printf("%d", max(dp[1][0], dp[1][1]));
    return 0;
}