Title

CodeForces 1401 D. Maximum Distributed Tree

Time Limit

2 seconds

Memory Limit

256 megabytes

Problem Description

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:

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

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

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

Sample 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

Sample Onput

17 18 286

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

Source

CodeForces 1401 D. Maximum Distributed Tree

题意

给一棵树你可以任意分配边权

但要使得所有边权乘积 $==k$

k是按质因子形式给出

设 $f(i,j)$ 是 $i$ 与 $j$ 路径边权和。

要使得所有点对边权和 $\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n f(i,j)$ 最大。

思路

经典所有点对边权和，对每条边来说贡献就是左边点的个数*右边点的个数。

求出来排个序。

对于 $k$ 来说

如果他的质因子个数不足 $n-1$ 则补 $1$ 即可

如果超过 $n-1$ 呢？

则思考两两乘起来合并

是大的两两合并更优（粗略证明

设质因子为 $p0 p1 p2$

边数贡献为 $c0c1$

均从大到小排序

则 $p0*c0+p1*c0+p2*c1>p0*c0+p1*c1+p2*c1$

则合并即可

最后对应相乘就是答案，别忘了取模 $10^9+7$

AC代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int maxn = 3e5 + 5; const ll inf = 0x3f3f3f3f; const ll mod = 1e9 + 7; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void dfs(int now, int fa, vector<vector<int>> &edge, vector<ll> &c, vector<ll> &sz, int n) { sz[now] = 1; for (auto &it : edge[now]) { if (it == fa) continue; dfs(it, now, edge, c, sz, n); sz[now] += sz[it]; } c.emplace_back(sz[now] * (n - sz[now])); } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int T; cin >> T; while (T--) { int n; cin >> n; vector<vector<int>> edge(n + 1, vector<int>()); for (int i = 1, u, v; i < n; ++i) { cin >> u >> v; edge[u].emplace_back(v); edge[v].emplace_back(u); } int m; cin >> m; deque<ll> dq(m); for (auto &it : dq) cin >> it; sort(all(dq), greater<ll>()); while (dq.size() > n - 1) { dq[1] = dq[0] * dq[1] % mod; dq.pop_front(); } while (dq.size() < n - 1) dq.push_back(1); vector<ll> c, sz(n + 1); dfs(1, 0, edge, c, sz, n); sort(all(c), greater<ll>()); ll ans = 0; for (int i = 0; i < n - 1; ++i) { ans = (ans + c[i] * dq[i] % mod) % mod; } cout << ans << endl; } return 0; }