BOJ. Independent Set of Tree. (2213)

Problem: BOJ 2213 — Tree Independent Set · 한국어 · 日本語

Root the tree at vertex 1. For each vertex v, let in[v] be the maximum weight of an independent set in the subtree of v that includes v, and out[v] the maximum when it excludes v. If w[v] is its positive weight, then

• in[v] = w[v] + sum(out[child]): choosing v rules out each child.
• out[v] = sum(max(in[child], out[child])): without v, each child may be chosen or omitted independently.

The graph is a tree, so the child subtrees have no edges between them; these choices therefore combine to give an optimum. Build a parent array and a root-first vertex order iteratively, then process that order backwards so every child DP value is ready before its parent. This avoids recursion and remains safe for a chain of 100,000 vertices.

Reconstruct by walking the rooted tree from the root. If the parent was chosen, the current vertex must be omitted. Otherwise, choose it only when in[v] > out[v]; on a tie omit it. The root follows the same rule. Either choice on a tie is optimal, and this fixed rule simply makes the output deterministic. Finally sort the chosen vertex IDs before printing them. The total weight is the root’s larger DP value; the second output line is one corresponding independent set.

Each vertex and edge is processed a constant number of times, so the time and space complexities are both O(N).

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine().trim());

        int[] weight = new int[n + 1];
        StringTokenizer weights = new StringTokenizer(input.readLine());
        for (int vertex = 1; vertex <= n; vertex++) {
            weight[vertex] = Integer.parseInt(weights.nextToken());
        }

        List<Integer>[] graph = new ArrayList[n + 1];
        for (int vertex = 1; vertex <= n; vertex++) {
            graph[vertex] = new ArrayList<>();
        }
        for (int edge = 0; edge < n - 1; edge++) {
            StringTokenizer tokens = new StringTokenizer(input.readLine());
            int a = Integer.parseInt(tokens.nextToken());
            int b = Integer.parseInt(tokens.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }

        int[] parent = new int[n + 1];
        int[] order = new int[n];
        int size = 0;
        order[size++] = 1;
        parent[1] = -1;
        for (int index = 0; index < size; index++) {
            int vertex = order[index];
            for (int next : graph[vertex]) {
                if (next == parent[vertex]) {
                    continue;
                }
                parent[next] = vertex;
                order[size++] = next;
            }
        }

        long[] in = new long[n + 1];
        long[] out = new long[n + 1];
        for (int index = n - 1; index >= 0; index--) {
            int vertex = order[index];
            in[vertex] = weight[vertex];
            for (int next : graph[vertex]) {
                if (parent[next] == vertex) {
                    in[vertex] += out[next];
                    out[vertex] += Math.max(in[next], out[next]);
                }
            }
        }

        boolean[] selected = new boolean[n + 1];
        int[] traversal = new int[n];
        int top = 0;
        traversal[top++] = 1;
        long optimum = Math.max(in[1], out[1]);
        while (top > 0) {
            int vertex = traversal[--top];
            int p = parent[vertex];
            selected[vertex] = p == -1
                    ? in[vertex] > out[vertex]
                    : !selected[p] && in[vertex] > out[vertex];
            for (int next : graph[vertex]) {
                if (parent[next] == vertex) {
                    traversal[top++] = next;
                }
            }
        }

        List<Integer> answer = new ArrayList<>();
        for (int vertex = 1; vertex <= n; vertex++) {
            if (selected[vertex]) {
                answer.add(vertex);
            }
        }
        Collections.sort(answer);

        StringBuilder output = new StringBuilder();
        output.append(optimum).append('\n');
        for (int vertex : answer) {
            output.append(vertex).append(' ');
        }
        System.out.println(output);
    }
}