← 返回题目列表

Codeforces · 1401/D

D. 最大分布式树

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 节点组成的树。您应该用满足以下条件的整数来标记其每个 $$$n-1$$$ 边:

- 每个整数必须大于 $$$0$$$;
- 所有 $$$n-1$$$ 数字的乘积应等于 $$$k$$$;
- 所有 $$$n-1$$$ 整数中 $$$1$$$-s 的数量必须尽可能小。

让我们将 $$$f(u,v)$$$ 定义为从节点 $$$u$$$ 到节点 $$$v$$$ 的简单路径上的数字之和。另外,令 $$$\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n f(i,j)$$$ 为树的分布索引。

找到你可以获得的最大可能的分布指数。由于答案可能太大,请以 $$$10^9 + 7$$$ 为模打印它。

在这个问题中,由于数字 $$$k$$$ 可能很大,因此给出 $$$k$$$ 素因数分解的结果。

输入

第一行包含一个整数 $$$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 < 6 \cdot 10^4$$$) 使得 $$$k = p_1 \cdot p_2 \cdot \ldots \cdot p_m$$$。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$,所有测试用例的$$$m$$$总和不超过$$$6 \cdot 10^4$$$,并且每个测试用例的给定边形成一棵树。

输出

打印您可以获得的最大分布指数。由于答案可能太大,请以 $$$10^9+7$$$ 为模打印它。

示例

输入 #1

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

输出 #1

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