P4516 [JSOI2018]潜入行动

    • 350通过
    • 1.2K提交
  • 题目提供者 和泉正宗
  • 评测方式 云端评测
  • 标签 背包 各省省选 2018 江苏 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    外星人又双叒叕要攻打地球了,外星母舰已经向地球航行!这一次,JYY 已经联系好了黄金舰队,打算联合所有 JSOIer 抵御外星人的进攻。

    在黄金舰队就位之前,JYY 打算事先了解外星人的进攻计划。现在,携带了监听设备的特工已经秘密潜入了外星人的母舰,准备对外星人的通信实施监听。

    外星人的母舰可以看成是一棵 $n$ 个节点、 $n-1$ 条边的无向树,树上的节点用 $1,2,\cdots,n$ 编号。JYY 的特工已经装备了隐形模块,可以在外星人母舰中不受限制地活动,可以神不知鬼不觉地在节点上安装监听设备。

    如果在节点 $u$ 上安装监听设备,则 JYY 能够监听与 $u$ 直接相邻所有的节点的通信。换言之,如果在节点 $u$ 安装监听设备,则对于树中每一条边 $(u,v)$ ,节点 $v$ 都会被监听。特别注意放置在节点 $u$ 的监听设备并不监听 $u$ 本身的通信,这是 JYY 特别为了防止外星人察觉部署的战术。

    JYY 的特工一共携带了 $k$ 个监听设备,现在 JYY 想知道,有多少种不同的放置监听设备的方法,能够使得母舰上所有节点的通信都被监听?为了避免浪费,每个节点至多只能安装一个监听设备,且监听设备必须被用完

    输入输出格式

    输入格式:

    输入第一行包含两个整数 $n,k$ ,表示母舰节点的数量 $n$ 和监听设备的数量 $k$ 。 接下来 $n-1$ 行,每行两个整数 $u,v$ $(1\le u,v\le n)$,表示树中的一条边。

    输出格式:

    输出一行,表示满足条件的方案数。因为答案可能很大,你只需要输出答案 $\text{mod 1,000,000,007}$ 的余数即可。

    输入输出样例

    输入样例#1: 复制
    5 3
    1 2
    2 3
    3 4
    4 5
    输出样例#1: 复制
    1

    说明

    样例 1 解释

    样例数据是一条链 $1-2-3-4-5$ 。首先,节点 $2$ 和 $4$ 必须放置监听设备,否则 $1,5$ 将无法被监听(放置的监听设备无法监听它所在的节点)。剩下一个设备必须放置在 $3$ 号节点以同时监听 $2,4$ 。因此在 $2,3,4$ 节点放置监听设备是唯一合法的方案。

    数据范围

    存在 $10\%$ 的数据,$1 \le n \le 20$ ;

    存在另外 $10\%$ 的数据,$1 \le n \le 100$ ;

    存在另外 $10\%$ 的数据,$1 \le k \le 10$ ;

    存在另外 $10\%$ 的数据,输入的树保证是一条链;

    对于所有数据,$1\le n\le 10^5$​ ,$1\le k\le \min\{n,100\}$ 。

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