P14911 [NHSPC 2024] 指纹

彼得是一个生物专家，他从不同的资料中分析同一群物种间的演化关系，经常会得到不同的演化树，他想知道不同演化树间的相似程度。为了节省比较时间，他的想法是先将每一棵演化树 $T$ 的结构用一个称为「指纹 (fingerprint)」的数字来表示，然后再进一步去仔细比较「指纹」相近的不同演化树。 演化树是一棵无向无根树 (undirected, unrooted tree)，叶节点代表现存物种。令 $S$ 是一个现存物种集合，令 $T$ 是 $S$ 的一棵演化树；也就是说 $T$ 的叶节点集合是 $S$；令 $\text{deg}(x)$ 表示与节点 $x$ 相邻之节点个数，对于一个点 $x \in T$，当 $\text{deg}(x) = 1$ 时，我们称 $x$ 为 $T$ 的叶节点；而不是叶节点的点就称作内节点，代表着物种的演化过程。对任两个物种 $x, y\in S$，定义它们间的距离 $d(x, y)$ 为 $x$ 到 $y$ 路径 (path) 上的边数 (number of edges)。彼得用 $f(T)$ 来表示 $T$ 的「指纹」并定义 $T$ 的「指纹」为任两物种距离平方的总和；也就是说 $$ f(T) = \sum_{x, y \in S, x < y} d(x, y)^2。 $$ 以下图中的演化树 $T$ 为例，这个演化树的「指纹」 $f(T) = d(1, 2)^2 + d(1, 3)^2 + d(1, 4)^2 + d(1, 5)^2 + d(2, 3)^2 + d(2, 4)^2 + d(2, 5)^2 + d(3, 4)^2 + d(3, 5)^2 + d(4, 5)^2 = 3^2 + 3^2 + 3^2 + 3^2 + 4^2 + 4^2 + 2^2 + 2^2 + 4^2 + 4^2 = 108$。 :::align{center}  ::: 请撰写一个程序来计算一棵演化树 $T$ 的「指纹」 $f(T)$。因为 $f(T)$ 可能很大，所以你只要求出 $f(T)$ 除以 $10^9 + 7$ 的余数。

$$\begin{aligned} &m \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{m-1} \ v_{m-1} \end{aligned}$$ * $m$ 代表演化树 $T$ 的点数量。 * $u_i$ 和 $v_i$ 代表的是在 $T$上 $u_i$ 和 $v_i$ 有一条边。

$$a$$ * $a$ 代表给定的演化树 $T$ 的指纹除以 $10^9 + 7$ 的余数。

### 数据限制 * $2 \le m \le 10^6$。 * $1 \le u_i, v_i \le m$。 * 输入的数皆为整数。 * 保证给定的图是一棵连通的演化树。 ### 评分说明 本题共有三组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 7 | $m \le 1000$。 | | 2 | 31 | 演化树的所有内部节点 $v$ 的 deg($v$) 都等于 $3$，$m \le 10^5$。 | | 3 | 62 | 无额外限制。 |