UOJ Logo

NOI.AC

1S 512MB

#2468. 树

统计

从前有棵 $n$ 个节点的树。

我们定义 $f(l,r)$ 为保留这棵树上所有编号在 $l$ 和 $r$ 之间的点的时候,连通块的个数。

现在你的任务是求出下面这个式子:

$$\sum_{i=1}^n\sum_{j=i}^nf^k(i,j)$$

虽然答案不会非常大,但是为了让它更像一个计数题,你还是要输出答案对 $10^9+9$ 取模的值。

输入格式

第一行两个整数 $n,k$。

接下来 $n-1$ 行,每一行两个整数 $u,v$,描述一条树边。

输出格式

输出一行一个整数,表示答案对 $10^9+9$ 取模的值。

样例1

Input

4 2
1 2
2 3
2 4

Output

13

样例解释

输入样例中的树长成下面这个样子:

Xprp-3kECXh-WDY1_cejhyCI2mawh99OGpppVGjJ

$f(1,1)=f(2,2)=f(3,3)=f(4,4)=1$,因为只有一个点。

$f(1,2)=f(1,3)=f(1,4)=f(2,3)=f(2,4)=1$,因为这些区间内的点都形成了一个连通块。

$f(3,4)=2$,因为 $3$ 和 $4$ 之间没有边相连。

所以答案就是 $1^2\times 9+2^2\times 1=13$。

数据范围

对于 $10\%$ 的数据,保证 $1\le n\le 100$;

对于 $30\%$ 的数据,保证 $1\le n\le 5000$;

对于另外 $20\%$ 的数据,保证所有的点形成了一条链;

对于另外 $20\%$ 的数据,保证 $k=1$;

对于 $100\%$ 的数据,保证 $1\le n\le 100000,1\le k\le 2$。

样例数据下载