P3698 [CQOI2017]小Q的棋盘

    • 197通过
    • 503提交
  • 题目提供者 XZYQvQ
  • 评测方式 云端评测
  • 标签 枚举,暴力 背包 贪心 连通块 各省省选 2017 重庆
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小 Q 正在设计一种棋类游戏。

    在小 Q 设计的游戏中,棋子可以放在棋盘上的格点中。某些格点之间有连线,棋子只能在有连线的格点之间移动。整个棋盘上共有 V 个格点,编号为0,1,2 … , V− 1,它们是连通的,也就是说棋子从任意格点出发,总能到达所有的格点。小 Q 在设计棋盘时,还保证棋子从一个格点移动到另外任一格点的路径是唯一的。

    小 Q 现在想知道,当棋子从格点 0 出发,移动 N 步最多能经过多少格点。格点可以重复经过多次,但不重复计数。

    输入输出格式

    输入格式:

    第一行包含2个正整数V, N,其中 V 表示格点总数,N 表示移动步数。

    接下来V − 1行,每行两个数 $a_i,b_i$ ,表示编号为 $a_i,b_i$ 的两个格点之间有连线。

    输出格式:

    输出一行一个整数,表示最多经过的格点数量。

    输入输出样例

    输入样例#1: 复制
    5 2
    1 0
    2 1
    3 2
    4 3
    输出样例#1: 复制
    3
    输入样例#2: 复制
    9 5
    0 1
    0 2
    2 6
    4 2
    8 1
    1 3
    3 7
    3 5
    输出样例#2: 复制
    5

    说明

    【输入输出样例 1 说明】

    从格点 0 出发移动 2 步。经过 0, 1, 2 这 3 个格点。

    【输入输出样例 2 说明】

    一种可行的移动路径为 0 → 1 → 3 → 5 → 3 → 7,经过 0, 1, 3, 5, 7 这 5 个格点。

    【数据规模与约定】

    对于 100%的测试点,N,V ≤ 100, 0 ≤a_i,b_i< V

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。