题解 | 旅游

树形dp

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int s = in.nextInt();
        ArrayList<HashSet<Integer>> map = new ArrayList<>();
        for (int i = 0; i <= n; i++) map.add(new HashSet<>());
        int u, v;
        for (int i = 0; i < n - 1; i++) {
            u = in.nextInt();
            v = in.nextInt();
            map.get(u).add(v);
            map.get(v).add(u);
        }
        boolean[] isvisited = new boolean[n + 1];

        int[][] dp = new int[n +
                             1][2]; //dp[i][0] 表示如果不住在i，以i为根的子树能旅游的最长时间
        dfs(map, dp, isvisited, s);
        System.out.println(dp[s][1]);
    }

    private static void dfs(ArrayList<HashSet<Integer>> map, int[][] dp,
                             boolean[] isvisited, int curCity) {
        isvisited[curCity] = true;
        for (int child : map.get(curCity)) {
            if (isvisited[child]) continue;
            dfs(map, dp, isvisited, child);
            dp[curCity][0] += Math.max(dp[child][0],dp[child][1]);
            dp[curCity][1] += dp[child][0];
        }
        dp[curCity][1]++; // 如果住在当前城市，至少要住 1 天
    }
}