欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构算法(树的比边权乘积=k)

程序员文章站 2022-03-03 22:09:37
TitleCodeForces 1401 D. Maximum Distributed TreeTime Limit2 secondsMemory Limit256 megabytesProblem DescriptionYou are given a tree that consists of nnn nodes. You should label each of its n−1n-1n−1 edges with an integer in such way that satisfies t...

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 nn nodes. You should label each of its n1n-1 edges with an integer in such way that satisfies the following conditions:

Let’s define f(u,v)f(u,v) as the sum of the numbers on the simple path from node uu to node vv. Also, let i=1n1j=i+1nf(i,j)\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 109+710^9 + 7.

In this problem, since the number kk can be large, the result of the prime factorization of kk is given instead.

Input

The first line contains one integer tt (1t1001 \le t \le 100) — the number of test cases.

The first line of each test case contains a single integer nn (2n1052 \le n \le 10^5) — the number of nodes in the tree.

Each of the next n1n-1 lines describes an edge: the ii-th line contains two integers uiu_i and viv_i (1ui,vin1 \le u_i, v_i \le n; uiviu_i \ne v_i) — indices of vertices connected by the ii-th edge.

Next line contains a single integer mm (1m61041 \le m \le 6 \cdot 10^4) — the number of prime factors of kk.

Next line contains mm prime numbers p1,p2,,pmp_1, p_2, \ldots, p_m (2pi<61042 \le p_i < 6 \cdot 10^4) such that k=p1p2pmk = p_1 \cdot p_2 \cdot \ldots \cdot p_m.

It is guaranteed that the sum of nn over all test cases doesn’t exceed 10510^5, the sum of mm over all test cases doesn’t exceed 61046 \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 109+710^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)=1f(1,2)=1, f(1,3)=3f(1,3)=3, f(1,4)=5f(1,4)=5, f(2,3)=2f(2,3)=2, f(2,4)=4f(2,4)=4, f(3,4)=2f(3,4)=2, so the sum of these 66 numbers is 1717.

In the second test case, one of the optimal ways is on the following image:

In this case, f(1,2)=3f(1,2)=3, f(1,3)=1f(1,3)=1, f(1,4)=4f(1,4)=4, f(2,3)=2f(2,3)=2, f(2,4)=5f(2,4)=5, f(3,4)=3f(3,4)=3, so the sum of these 66 numbers is 1818.

Source

CodeForces 1401 D. Maximum Distributed Tree

题意

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

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

k是按质因子形式给出

f(i,j)f(i,j)iijj路径边权和。

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

思路

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

求出来排个序。

对于kk来说

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

如果超过n1n-1呢?

则思考两两乘起来合并

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

设质因子为p0p1p2p0 p1 p2

边数贡献为c0c1c0c1

均从大到小排序

p0c0+p1c0+p2c1>p0c0+p1c1+p2c1p0*c0+p1*c0+p2*c1>p0*c0+p1*c1+p2*c1

则合并即可

最后对应相乘就是答案,别忘了取模109+710^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

相关标签: 数据结构 算法