← 返回题目列表

Codeforces · 1540/B

B. 树形数组

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 节点组成的树。通过一一标记节点,可以从树中生成一个数组。

最初,当没有节点被标记时,从整棵树中等概率地选择并标记一个节点。

之后,直到所有节点都被标记,从一组未标记节点中等概率地选择并标记一个节点,该节点与标记节点至少有一条边。

可以看出,该过程标记了树中的所有节点。

最终数组 $$$a$$$ 是按每个节点被标记的时间顺序排列的节点标签列表。

查找由树和上述过程生成的数组中的预期反转次数。

数组 $$$a$$$ 中的反转数是满足 $$$i < j$$$ 且 $$$a_i > a_j$$$ 的索引对 $$$(i, j)$$$ 的数量。例如,数组 $$$[4, 1, 3, 2]$$$ 包含 $$$4$$$ 反转:$$$(1, 2)$$$、$$$(1, 3)$$$、$$$(1, 4)$$$、$$$(3, 4)$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 200$$$) — 树中的节点数。

接下来的 $$$n - 1$$$ 行每行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$; $$$x \neq y$$$),表示节点 $$$x$$$ 和 $$$y$$$ 之间的边。

保证给定的边形成一棵树。

输出

输出生成的数组中预期的反转数,模 $$$10^9+7$$$。

正式地,令 $$$M = 10^9+7$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

示例

输入 #1

3
1 2
1 3

输出 #1

166666669

输入 #2

6
2 1
2 3
6 1
1 4
2 5

输出 #2

500000009

输入 #3

5
1 2
1 3
1 4
2 5

输出 #3

500000007

注意

这是第一个样本中的树:

对于第一个示例,数组几乎是固定的。如果最初选择节点 $$$2$$$,则唯一可能的数组是 $$$[2, 1, 3]$$$ ($$$1$$$ 反转)。如果最初选择节点 $$$3$$$,则唯一可能的数组是 $$$[3, 1, 2]$$$ ($$$2$$$ 反转)。如果最初选择节点 $$$1$$$,则数组 $$$[1, 2, 3]$$$ ($$$0$$$ 反转)和 $$$[1, 3, 2]$$$ ($$$1$$$ 反转)是唯一的可能性和等概率。总共,预期的反转次数为 $$$\frac{1}{3}\cdot 1 + \frac{1}{3} \cdot 2 + \frac{1}{3} \cdot (\frac{1}{2} \cdot 0 + \frac{1}{2} \cdot 1) = \frac{7}{6}$$$。

$$$166666669 \cdot 6 = 7 \pmod {10^9 + 7}$$$,所以答案是$$$166666669$$$。

这是第二个样本中的树:

这是第三个样本中的树: