题解 | 旅游

import java.io.*;
import java.util.*;

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

        List<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(reader.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            adj[x].add(y);
            adj[y].add(x);
        }

        List<Integer>[] children = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            children[i] = new ArrayList<>();
        }
        int[] parent = new int[n + 1];
        Arrays.fill(parent, -1);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        parent[s] = 0; 

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj[u]) {
                if (parent[v] == -1) {
                    parent[v] = u;
                    children[u].add(v);
                    queue.add(v);
                }
            }
        }

        int[] dp0 = new int[n + 1];
        int[] dp1 = new int[n + 1];
        Stack<Integer> stack = new Stack<>();
        stack.push(s);
        boolean[] processed = new boolean[n + 1];

        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (!processed[u]) {
                processed[u] = true;
                stack.push(u);
                for (int i = children[u].size() - 1; i >= 0; i--) {
                    stack.push(children[u].get(i));
                }
            } else {
                dp1[u] = 1;
                dp0[u] = 0;
                for (int v : children[u]) {
                    dp1[u] += dp0[v];
                    dp0[u] += Math.max(dp0[v], dp1[v]);
                }
            }
        }

        System.out.println(dp1[s]);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1.输入处理：使用BufferedReader和StringTokenizer高效读取输入数据，构建邻接表表示的树结构。

2.有根树构建：通过BFS遍历，以起始城市s为根，确定每个节点的父节点和子节点列表。

3.动态规划计算：使用栈模拟后序遍历，计算每个节点的dp0和dp1值，确保在处理每个节点时，其子节点已被处理完毕。

4.结果输出：输出起始城市s的dp1[s]值，即为包含s的最大独立集大小，即最多能度过的天数。