CF1401D.Maximum Distributed Tree

You are given a tree that consists of $n$ nodes. You should label each of its $n-1$ edges with an integer in such way that satisfies the following conditions:

• each integer must be greater than $0$;
• the product of all $n-1$ numbers should be equal to $k$;
• the number of $1$-s among all $n-1$ integers must be minimum possible.

Let's define $f(u,v)$ as the sum of the numbers on the simple path from node $u$ to node $v$. Also, let $\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n f(i,j)$ be a distribution index of the tree.

Find the maximum possible distribution index you can get. Since answer can be too large, print it modulo $10^9 + 7$.

In this problem, since the number $k$ can be large, the result of the prime factorization of $k$ is given instead.

你将得到一棵包含 $n$ 个节点的树。你需要为它的 $n-1$ 条边分别标上一个正整数，使得满足以下条件：

• 每个整数必须大于 $0$；
• 所有 $n-1$ 个整数的乘积恰好等于 $k$；
• 在所有 $n-1$ 个整数中，数字 $1$ 的个数应尽可能少。

定义 $f(u,v)$ 为从节点 $u$ 到节点 $v$ 的简单路径上所有边权值之和。再定义 $\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n f(i,j)$ 为该树的分配指数（distribution index）。

请找出所能达到的最大分配指数。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

在本题中，由于 $k$ 可能很大，输入直接给出 $k$ 的质因数分解结果。

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the number of nodes in the tree.

Each of the next $n-1$ lines describes an edge: the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$; $u_i \ne v_i$) — indices of vertices connected by the $i$-th edge.

Next line contains a single integer $m$ ($1 \le m \le 6 \cdot 10^4$) — the number of prime factors of $k$.

Next line contains $m$ prime numbers $p_1, p_2, \ldots, p_m$ ($2 \le p_i \lt 6 \cdot 10^4$) such that $k = p_1 \cdot p_2 \cdot \ldots \cdot p_m$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$, the sum of $m$ over all test cases doesn't exceed $6 \cdot 10^4$, and the given edges for each test cases form a tree.

第一行包含一个整数 $t$（$1 \le t \le 100$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— 树中节点的数量。

接下来的 $n-1$ 行每行描述一条边：第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$；$u_i \ne v_i$）—— 表示由第 $i$ 条边连接的两个顶点的编号。

下一行包含一个整数 $m$（$1 \le m \le 6 \cdot 10^4$）—— $k$ 的质因数个数。

再下一行包含 $m$ 个质数 $p_1, p_2, \ldots, p_m$（$2 \le p_i \lt 6 \cdot 10^4$），满足 $k = p_1 \cdot p_2 \cdot \ldots \cdot p_m$。

保证所有测试用例的 $n$ 之和不超过 $10^5$，所有测试用例的 $m$ 之和不超过 $6 \cdot 10^4$，且每个测试用例给出的边构成一棵树。

Print the maximum distribution index you can get. Since answer can be too large, print it modulo $10^9+7$.

输出你能得到的最大分配指数。由于答案可能过大，请对 $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$.

在第一个测试用例中，一种最优方案如下图所示：

此时，$f(1,2)=1$，$f(1,3)=3$，$f(1,4)=5$，$f(2,3)=2$，$f(2,4)=4$，$f(3,4)=2$，因此这 $6$ 个数的和为 $17$。

在第二个测试用例中，一种最优方案如下图所示：

此时，$f(1,2)=3$，$f(1,3)=1$，$f(1,4)=4$，$f(2,3)=2$，$f(2,4)=5$，$f(3,4)=3$，因此这 $6$ 个数的和为 $18$。