徐老师的星形图

文件读写

• 输入文件star.in
• 输出文件star.out

限制

• 1000ms
• 512MB

题目描述

徐老师最近又又又在复习图论了！在复习 $spfa$ 的时候，他看到了一种图——菊花图

菊花图是一种很有趣的图，它的形状类似于一朵菊花，正中间一个点，然后这个点和其他所有点存在一条边相连

于是徐老师突发奇想，如果存在一种不那么标准的菊花图呢？

也就是正中间依旧是一个点，但是这个点连接出去的点可以向外继续延伸，比如下图

形式化的说，也就是在一个连通图 $G$ 中，当且仅当 $G$ 存在恰好一个度数 $\ge 3$ 的结点，那么徐老师就认为 $G$ 是一个星形图

现在徐老师准备给你降低一点难度，他打算给你一棵包含了 $n$ 个点的树，希望你删除其中一部分点（可以不删）后，使得剩余的点会变成一个星形图。

请你告诉徐老师有多少种不同的方案。

输入格式

输入第一行包含一个整数 $n$，表示这棵树的节点数量

接下来 $n-1$ 行每行包含两个整数 $u,v$ 表示一条树边

输出格式

输出第一行包含一个整数，表示方案数，由于答案可能过大，请你将答案对 $1e9+7$ 取模后输出

数据范围

对于 $20\%$ 的数据满足 $n \le 15$。

对于 $40\%$ 的数据满足 $n \le 2000$。

对于另外 $10\%$ 的数据满足 $u_i=i,v_i=i+1$

对于另外 $10\%$ 的数据满足 $u_i=1,v_i=i+1$

对于另外 $10\%$ 的数据保证给定的树为星形图

对于所有数据满足：$1 \leq n \leq 5 * 10^5$，且保证给定的边构成一棵树

样例输入1

6
1 2
1 3
1 4
1 5
1 6

样例输出1

16

样例解释1

由于本身就是一个星形图，所以除 $1$ 之外只要保留任意 $3$ 个节点都是一组可行方案

不删的方案为 $1$ 删 $1$ 个点的方案为 $5$ 删 $2$ 个点的方案为 $5 * 4 / 2 = 10$ 一共有 $16$ 种方案

样例输入2

6
1 2
1 3
1 4
3 5
3 6

样例输出2

6

样例解释2

如果以 $1$ 为中心点，$5,6$ 至少删一个即可，有 $3$ 种方案

如果以 $3$ 为中心点，$2,4$ 至少删一个即可，有 $3$ 种方案

一共 $6$ 种方案