You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一棵 $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$ 取模后的值。

3
4
1 2
2 3
3 4
2
2 2
4
3 4
1 3
3 2
2
3 2
7
6 1
2 3
4 6
7 3
5 1
3 6
4
7 5 13 3

17
18
286

样例解释

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

在这个用例中，(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。