#1112. 「HNOI 2018 省队集训 Day 3」admirable

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: KSkun

题目描述

众所周知, 小 a 非常 admirable , 因此他有很多的仰慕者

小 a 有一个地盘, 他的地盘恰好是一棵 n 个节点的树, 作为 admirable 的小 a , 他可以分配k个仰慕者在他的地盘上进行巡逻, 每个仰慕者的巡逻的路径都是树上的一条简单路径

由于小 a 有时候要召集仰慕者们来做一些别的事情, 所以小 a 规定所有仰慕者的巡逻路径至少有一条公共边

同时, 小 a 为了维护他的 admirable , 他不允许存在一条边恰好被 m \in [2, k - 1] 个仰慕者巡逻

此外, 小 a 为了让他变得更加 admirable , 他允许存在边没有被巡逻(当然也可以所有边都被巡逻)

最让人 admirable 的是, 小 a 可以 1 秒内脑补出安排仰慕者的巡逻路径的方案数, 不过为了验证正确性以免装 b 失败, 小 a 要你再计算一下

注意, 对于巡逻路径 (a, b) (b, a) 是等价的

由于仰慕者是两两不同的, 所以两个方案不同当且仅当至少存在一个仰慕者在这两个方案中的巡逻路径不同

输入格式

第一行 n, k 接下来 n - 1 行, 第 i 行为 u_i, v_i , 表示一条边连接 u_i, v_i

输出格式

一行一个数, 表示方案数对 10^9 + 9 (1000000009) 取模的结果

样例

样例 1 输入

3 2
2 3
1 2

样例 1 输出

7

样例解释

方案如下:

  1. ((1, 2), (1, 2))
  2. ((1, 2), (1, 3))
  3. ((1, 3), (1, 2))
  4. ((1, 3), (1, 3))
  5. ((1, 3), (2, 3))
  6. ((2, 3), (1, 3))
  7. ((2, 3), (2, 3))

本题有附加样例,请自行下载。

数据范围与提示

对于 10\% 的数据, 1 \leq n, k \leq 5

对于 30\% 的数据, 1 \leq n, k \leq 100

对于 60\% 的数据, 1 \leq n, k \leq 5000

对于另外 20\% 的数据, 树的形态为链

对于 100\% 的数据, 1 \leq n, k \leq 10^5

出题人:膜Cai小组

来源:HNOI 2018 省队集训 Day 3 T2