#PQJ164x520. QOJ 164_520

    ID: 2678 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JSOI 2018动态规划树上算法

QOJ 164_520

潜入行动 (action) 潜入行动 (action) 【故事背景】 外星人又双叒叕要攻打地球了,外星母舰已经向地球航行!这一次,JYY 已 经联系好了黄金舰队,打算联合所有JSOIer 抵御外星人的进攻。在黄金舰队就 位之前,JYY 打算事先了解外星人的进攻计划。现在,携带了监听设备的特工已 经秘密潜入了外星人的母舰,准备对外星人的通信实施监听。 【问题描述】 外星人的母舰可以看成是一棵𝑛个节点、𝑛−1条边的无向树,树上的节点用 1,2, … , 𝑛编号。JYY 的特工已经装备了隐形模块,可以在外星人母舰中不受限制 地活动,可以神不知鬼不觉地在节点上安装监听设备。 如果在节点𝑢上安装监听设备,则JYY 能够监听与𝑢直接相邻所有的节点的 通信。换言之,如果在节点𝑢安装监听设备,则对于树中每一条边(𝑢, 𝑣),节点𝑣 都会被监听。特别注意放置在节点𝑢的监听设备并不监听𝒖本身的通信,这是JYY 特别为了防止外星人察觉部署的战术。 JYY 的特工一共携带了𝑘个监听设备,现在JYY 想知道,有多少种不同的 放置监听设备的方法,能够使得母舰上所有节点的通信都被监听?为了避免浪费, 每个节点至多只能安装一个监听设备。 【输入格式】 输入第一行包含两个整数𝑛, 𝑘,表示母舰节点的数量𝑛和监听设备的数量𝑘。 接下来𝑛−1行,每行两个整数𝑢, 𝑣 (1 ≤𝑢, 𝑣≤𝑛),表示树中的一条边。 【输出格式】 输出一行,表示满足条件的方案数。因为答案可能很大,你只需要输出答案 mod 1,000,000,007 的余数即可。 【样例输入】 5 3

潜入行动 (action) 1 2 2 3 3 4 4 5 【样例输出】 1 【样例说明】 样例数据是一条链1 – 2 – 3 – 4 – 5。首先,节点2 和4 必须放置监听设备, 否则1, 5 将无法被监听(放置的监听设备无法监听它所在的节点)。剩下一个设备 必须放置在3 号节点以同时监听2, 4。因此在2, 3, 4 节点放置监听设备是唯一 合法的方案。 【数据规模】 存在10%的数据,1 ≤𝑛≤20; 存在另外10%的数据,1 ≤𝑛≤100; 存在另外10%的数据,1 ≤𝑘≤10; 存在另外10%的数据,输入的树保证是一条链; 对于所有数据,1 ≤𝑛≤10/, 1 ≤𝑘≤min{𝑛, 100}。