首页 > 试题广场 >

旅游

[编程题]旅游
  • 热度指数:2482 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
Cwbc和XHRlyb生活在 s 市,这天他们打算一起出去旅游。
旅行地图上有 n 个城市,它们之间通过 n-1 条道路联通。
Cwbc和XHRlyb第一天会在 s 市住宿,并游览与它距离不超过 1 的所有城市,之后的每天会选择一个城市住宿,然后游览与它距离不超过 1 的所有城市。
他们不想住在一个已经浏览过的城市,又想尽可能多的延长旅行时间。
XHRlyb想知道她与Cwbc最多能度过多少天的时光呢?
聪明的你在仔细阅读题目后,一定可以顺利的解决这个问题!

输入描述:
第一行,两个正整数n和s,表示城市个数和第一天住宿的城市s。
接下来n-1行,每行两个整数x和y,表示城市x与城市y之间有一条双向道路,保证无环。


输出描述:
第一行,一个非负整数表示答案。
示例1

输入

4 1
1 2
2 3
3 4

输出

2

说明

第一天,在1号城市住宿,游览了1、2号城市。
第二天,在3号城市住宿,游览了4号城市,旅行结束。

备注:
1 ≤ n ≤ 500000, 1 ≤ s, x, y ≤ n。
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];
        }
    }
}

发表于 2025-06-11 11:29:12 回复(0)