Maximum Distributed Tree
Contest: Codeforces Round 665 (Div. 2)
Difficulty rating: 1800
Tags: dfs and similar, dp, greedy, implementation, math, number theory, sortings, trees

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.

Input format:
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 < 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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
17
18
286

Editorial:
Let's define $$$w_i$$$ as the product of the number of vertices belonging to each of the two components divided when the $$$i_{th}$$$ edge is removed from the tree, and $$$z_i$$$ as the number on $$$i_{th}$$$ edge. Now a distribution index is equal to $$$\sum_{i=1}^{n-1}(w_i \times z_i)$$$. Now there are two cases:
$$$A$$$ : $$$m \le n-1$$$
In this case, we have to label $$$p_1, p_2, \ldots p_m$$$ to $$$m$$$ distinct edges because we have to minimize the number of $$$1$$$-s. And to maximize distribution index, we can label a larger $$$p_i$$$ to the edge in which $$$w_i$$$ is larger because the following holds:
$$$\bullet$$$ For four positive integers $$$a, b, c, d$$$ ($$$a \ge b, c \ge d$$$), $$$ac + bd \ge ad + bc$$$
Let's suppose $$$a=b+x, c=d+y$$$ $$$(x, y \ge 0)$$$. Then the equation can be written as follows:
$$$(b+x)(d+y)+bd \ge (b+x)d+b(d+y)$$$
$$$bd+by+xd+xy+bd \ge bd+xd+bd+by$$$
$$$xy \ge 0$$$
Because $$$x, y \ge 0$$$, we proved it.
And label $$$1$$$ to the remaining edges.
$$$B$$$ : $$$m > n-1$$$
In this case, we can make no $$$1$$$-s exist out of $$$n-1$$$ integers, and some of $$$n-1$$$ number would be composite. And to maximize distribution index, we can label the product of $$$m-n+2$$$ largest $$$p_i$$$ to the edge in which $$$w_i$$$ is largest, and label the remaining $$$p_i$$$ to the remaining edges in the same way as case $$$A$$$ because the following holds:
$$$\bullet$$$ For five positive integers $$$a, b, c, d, e$$$ ($$$a \ge b, d \ge e$$$), $$$acd+be \ge bcd+ae$$$
Substituting $$$f = cd$$$ in the above equation, we can find the equation is same as before. So we proved it.
After filling in the edge, calculate it and find the answer.
Time complexity : $$$O(\max(n, m) \log \max(n,m))$$$