U314350 saqriphrx

我就向你诉说诸灵王国的钥匙。 这把钥匙与Yetzirah【创世】的数值相同。 诸灵均依靠自然的万物与广布的阶层。 3 个掌控，3 个结束，及3 种媒介所述之灵分布于上，下，中： 若你欣喜攀登神圣阶梯，若你以延续替代上升，你必发现躯壳以外的相反层次，或逝者之灵。 仅你一人须知，无人知晓的天堂诸国的美德与权能。 这些均是诸灵升降于神圣阶梯的刻度。 Michael, Gabriel, Raphael,等其他，不是其名而为其权称。 ......

给定一棵树，每次操作删除所有直径端点中任意一点，直到这棵树变为一条链。求期望删除次数，答案对 $1e9+7$ 取模。

第一行输入整数 $n$，表示节点数。 接下来 $n-1$ 行，每行输入两个整数 $u,v$，表示 $u,v$ 之间有一条边。

输出期望次数，对 $1e9+7$ 取模。

得到链有如下情况： 第一次删除 $4$ 或 $5$ 号节点，期望：$\frac{2}{3}\times 1$。 第一次删除 $6$ 号节点，第二次删除 $4$ 或 $5$ 号节点，期望：$\frac{2}{9}\times 2$。 第一次删除 $6$ 号节点，第二次删除 $3$ 号节点，第三次删除任意直径端点，期望：$\frac{1}{9}\times 3$。 总期望：$\frac{13}{9}$。