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$ 为这些质数的乘积。

第一行，一个整数 $t$ $(1\leq t\leq 100)$，表示多组测试数据个数。对于每一个测试数据： 第一行，一个整数 $n$ $(2\leq n\leq 10^5)$，表示树上节点数； 第 $2$ 至 $n$ 行，每行两个整数 $u_i$ 和 $v_i$ $(1\leq u_i,v_i \leq n,u_i\neq v_i)$，描述了一条无向边； 第 $n+1$ 行，一个整数 $m$ $(1\leq m\leq 6\times 10^4)$，表示 $k$ 分解成质因子的个数； 第 $n+2$ 行，$m$ 个 **质数** $p_i$ $(2\leq p_i< 6\times 10^4)$，有 $k=\prod\limits_{i=1}^m p_i$。 数据保证所有的 $n$ 总和不超过 $10^5$，所有的 $m$ 总和不超过 $6\times 10^4$。数据给出的边保证能够形成一棵树。

一行，一个整数，表示最大的答案对 $10^9+7$ 取模后的值。

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 $ .