数据结构算法（树的比边权乘积=k）

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; } 

本文地址：https://blog.csdn.net/weixin_44354699/article/details/108162921