旅游

import java.util.*;

public class TreeTravel {
    // 最大节点数（根据题目数据范围调整）
    static final int MAX_N = 500001;
    // DP数组：dp[cur][0]表示不选当前节点的最大天数，dp[cur][1]表示选当前节点的最大天数
    static int[][] dp = new int[MAX_N][2];
    // 邻接表存储树结构 - 使用列表的列表替代泛型数组
    static List<List<Integer>> G = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int s = scanner.nextInt();

        // 初始化邻接表
        for (int i = 0; i <= n; i++) {
            G.add(new ArrayList<>()); // 每个节点对应一个邻接表
        }

        // 初始化DP数组：每个节点选自己时默认贡献1天（初始住宿天数）
        for (int i = 1; i <= n; i++) {
            dp[i][1] = 1; // 选当前节点时，至少有1天住宿（自己）
        }

        // 读取边并构建树
        for (int i = 1; i < n; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            G.get(u).add(v); // 无向树，双向添加
            G.get(v).add(u);
        }

        // 从起点s开始深度优先搜索，父节点初始为-1（无父节点）
        dfs(s, -1);

        // 输出结果：选起点s时的最大天数（第一天必须选s）
        System.out.println(dp[s][1]);
        scanner.close();
    }

    /**
     * 深度优先搜索计算DP值
     * @param cur 当前节点
     * @param pre 当前节点的父节点（避免回溯）
     */
    private static void dfs(int cur, int pre) {
        // 遍历当前节点的所有邻接节点
        for (int next : G.get(cur)) {
            if (next == pre) { // 跳过父节点，避免循环
                continue;
            }
            dfs(next, cur); // 递归处理子节点

            // 状态转移：不选当前节点cur时，子节点可以选或不选，取最大值
            dp[cur][0] += Math.max(dp[next][1], dp[next][0]);
            // 状态转移：选当前节点cur时，子节点不能选（只能取子节点不选的情况）
            dp[cur][1] += dp[next][0];
        }
    }
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int s = in.nextInt();
            HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
            for (int i = 0; i < n - 1; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                if (map.get(x) == null) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(y);
                    map.put(x, list);
                } else map.get(x).add(y);

                if (map.get(y) == null) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(x);
                    map.put(y, list);
                } else map.get(y).add(x);
            }
            int[][] dp = new int[n + 1][2];
            dfs(map, dp, s, -1);
            //System.out.println(Math.max(dp[s][0], dp[s][1])); 看清题目是s点放入 所以只有一种情况
            System.out.println( dp[s][1]);
        }
    }
    public static void dfs(HashMap<Integer, ArrayList<Integer>> map, int[][] dp,
                           int root, int pre) {
        dp[root][1] = 1;
        //root 当前结点 pre 父节点
        if (map.get(root) == null) {
            return; //叶结点
        }
        for (int i = 0; i < map.get(root).size(); i++) {
            int v = map.get(root).get(i); //子节点
            if (v == pre) continue; //找回到了根结点
            dfs(map, dp, v, root);
            dp[root][1] += dp[v][0];
            dp[root][0] += Math.max(dp[v][1], dp[v][0]);
        }
    }
}

cpp的vector在容量较大时，如果size == capacity需要分配更多内存，再次分配的空间是当前内存乘2，那个50w的用例可能一下次会分配太多😅