BOJ. Society Service(SNS) (2533)

[Link] https://www.acmicpc.net/problem/2533

Root the tree at vertex 0 and build a root-first order iteratively. Processing that order in reverse guarantees that every child has already been processed, so the dynamic program needs no recursive calls and remains safe on a chain of up to 10^6 vertices.

For each vertex u, notAdopter[u] is the minimum number of early adopters in its subtree when u is not one. In that case every child must be an early adopter, so this state is the sum of the children’s adopter states. adopter[u] is the minimum when u is an early adopter; each child can then use whichever state is cheaper, in addition to u itself. A leaf therefore has states (0, 1). This also handles the single-vertex tree: its answer is min(0, 1) = 0.

The adjacency lists, traversal order, and two DP states use primitive arrays. Each vertex and edge is processed a constant number of times, giving O(N) time and O(N) space.

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        int[] head = new int[n];
        int[] to = new int[2 * (n - 1)];
        int[] next = new int[2 * (n - 1)];
        java.util.Arrays.fill(head, -1);

        int edgeCount = 0;
        for (int i = 0; i < n - 1; i++) {
            int a = input.nextInt() - 1;
            int b = input.nextInt() - 1;
            to[edgeCount] = b;
            next[edgeCount] = head[a];
            head[a] = edgeCount++;
            to[edgeCount] = a;
            next[edgeCount] = head[b];
            head[b] = edgeCount++;
        }

        int[] parent = new int[n];
        int[] order = new int[n];
        int size = 1;
        order[0] = 0;
        parent[0] = -1;

        // Build a root-first order without recursion.
        for (int i = 0; i < size; i++) {
            int node = order[i];
            for (int edge = head[node]; edge != -1; edge = next[edge]) {
                int child = to[edge];
                if (child == parent[node]) {
                    continue;
                }
                parent[child] = node;
                order[size++] = child;
            }
        }

        int[] notAdopter = new int[n];
        int[] adopter = new int[n];
        for (int i = size - 1; i >= 0; i--) {
            int node = order[i];
            adopter[node] = 1;
            for (int edge = head[node]; edge != -1; edge = next[edge]) {
                int child = to[edge];
                if (child == parent[node]) {
                    continue;
                }
                notAdopter[node] += adopter[child];
                adopter[node] += Math.min(notAdopter[child], adopter[child]);
            }
        }

        System.out.println(Math.min(notAdopter[0], adopter[0]));
    }

    private static class FastScanner {
        private final BufferedInputStream in = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int pointer;
        private int length;

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ');

            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value;
        }

        private int read() throws IOException {
            if (pointer == length) {
                length = in.read(buffer);
                pointer = 0;
                if (length == -1) {
                    return -1;
                }
            }
            return buffer[pointer++];
        }
    }
}