백준 1949

문제

---

규칙

• '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.

• 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.

• 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

사실 3번째 조건을 별도로 체크해야하는지 고민했지만 그럴 필요 없었다.

만약 우수마을 선정 여부를 모르는 A가 있고, A와 인접한 모든 마을이 우수마을이 아니라고 가정하자. 
(1번과 2번 조건을 만족한다고 하자)

그렇다면 1번째 조건에 의해 당연히 A는 우수마을일 것이다.

우수마을 인구의 최대값을 구하는 중이기 때문에 
우수마을로 A를 포함시키는 것이 당연히 총 인구가 최대가 되고 2번 조건에 반하지도 않는다.

즉 결론은, 그냥 1번과 2번 조건을 만족시키면 3번 조건도 자동으로 만족되니까 크게 신경쓸 필요 없다는 것

---

dp[i][j] :

i번 노드를 루트노드로 가지는 서브트리에서, i번 노드의 우수마을 여부는 j일 때

우수마을 주민의 최대값 (j --> 1: 우수마을, 0: 우수마을 아님)

---

Code

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class P1949 {

	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
	static int[][] dp;
	static int[] population;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());
		visited = new boolean[N + 1];
		dp = new int[N + 1][2];
		population = new int[N + 1];

		for(int i = 0; i <= N; i++) {
			list.add(new ArrayList<Integer>());
		}

		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 1; i <= N; i++) {
			population[i] = Integer.parseInt(st.nextToken());
		} 

		for(int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list.get(a).add(b);
			list.get(b).add(a);
		}

		dfs(1);
		// dfs(1, -1);

		bw.write(String.valueOf(Math.max(dp[1][0], dp[1][1])));

		br.close();
		bw.flush();
		bw.close();
	}

	private static void dfs(int N) {
		visited[N] = true;
		dp[N][0] = 0;
		dp[N][1] = population[N];
		
		for(int child : list.get(N)) {
			if(!visited[child]) {
				dfs(child);

				dp[N][0] += Math.max(dp[child][0], dp[child][1]); 
				dp[N][1] += dp[child][0];
			}
		}
	}

	// visited 배열을 쓰지 않을 경우
    private static void dfs(int now, int parent) {
        for (int child : list.get(now)) {
            if (child != parent) {
                dfs(child, now);
                dp[now][0] += Math.max(dp[child][0], dp[child][1]);
                dp[now][1] += dp[child][0];
            }
        }
        dp[now][1] += population[now];
    }

}