CF1401D Maximum Distributed Tree

给定一棵 $n$ 个节点，$n-1$ 条边的树。你可以在每一条树上的边标上边权，使得： 1. 每个边权都为 **正整数**； 2. 这 $n-1$ 个边权的 **乘积** 等于 $k$； 3. 边权为 $1$ 的边的数量最少。 定义 $f(u,v)$ 表示节点 $u$ 到节点 $v$ 的简单路径经过的边权总和。你的任务是让 $\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} f(i,j)$ 最大。 最终答案可能很大，对 $10^9+7$ 取模即可。 $k$ 有可能很大，输入数据中包含了 $m$ 个质数 $p_i$，那么 $k$ 为这些质数的乘积。

无

无

In the first test case, one of the optimal ways is on the following image:  In this case, $ f(1,2)=1 $ , $ f(1,3)=3 $ , $ f(1,4)=5 $ , $ f(2,3)=2 $ , $ f(2,4)=4 $ , $ f(3,4)=2 $ , so the sum of these $ 6 $ numbers is $ 17 $ . In the second test case, one of the optimal ways is on the following image:  In this case, $ f(1,2)=3 $ , $ f(1,3)=1 $ , $ f(1,4)=4 $ , $ f(2,3)=2 $ , $ f(2,4)=5 $ , $ f(3,4)=3 $ , so the sum of these $ 6 $ numbers is $ 18 $ .