P10912 [蓝桥杯 2024 国 B] 数星星

小明正在一棵树上数星星，这棵树有 $n$ 个结点 $1, 2,\cdots, n$。他定义树上的一个子图 $G$ 是一颗星星，当且仅当 $G$ 同时满足： 1. $G$ 是一棵树。 2. $G$ 中存在某个结点，其度数为 $|V_G| - 1$。其中 $|V_G|$ 表示这个子图含有的结点数。 两颗星星不相同当且仅当它们包含的结点集合 $V_G$ 不完全相同。小明想知道这棵树上有多少颗不同的星星包含的结点的数量在区间 $[L, R]$ 中，答案对 $1000000007$ 取模。

无

无

**【样例说明】** 包含 $3$ 个结点的星星有 $5$ 个，它们的结点集合分别为 $\{1, 2, 3\}$，$\{1, 2, 4\}$，$\{1, 2, 5\}$，$\{2, 4, 5\}$，$\{1, 3, 6\}$。 包含 $4$ 个结点的星星有 $1$ 个，它的结点集合为 $\{1, 2, 4, 5\}$。 **【评测用例规模与约定】** 对于 $20\%$ 的评测用例，保证 $n \le 20$。 对于 $100\%$ 的评测用例，保证 $n \le 10^5$，$1 \le L \le R \le n$。