D. Maximum Distributed Tree
题意
给出一棵n个点n-1条边的树
现在要求给每条边赋值,
要求：
所有边的权值乘积为k,由于k比较大,给出k的素因子prime(有m个);
所有边权大于0;
令边权为1的边尽可能少;
现在要求树上任意两点的简单路径边权和最大
即$∑{i=1}^{n-1}(∑{j=i+1}^nf(i,j))$
定义$f(i,j)$为树上两点$(i,j)$ 简单路径的边权和
题解
显然要统计每条边权对答案产生的贡献
假设1号点为根 求出每个点的子树大小sz
则对于边$(i,j)$ 其中j为i的子节点
那么它将会被计入答案sz[i]×(n-sz[i])次
于是根据每条边被计入的次数vistime排序
被使用较多的优先分配更大的权值
由于m个素因子可能不能正好给n-1条边分配
于是根据题意首先对所有因子降序排列
若m<n-1那么剩下的边以1为边权
若m>n-1则将大的因子相乘合并为一个因子
反复操作使得最后存在n-1个因子最后分配给所有边
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e5+5;
const double Pi=acos(-1);
const ll Mod=1e9+7;
vector<int>mp[Max];
vector<ll>vistime;
ll sz[Max];
void dfs_size(int now,int fa){
for(auto i:mp[now]){
if(i==fa)continue;
dfs_size(i,now);
sz[now]+=sz[i];
}
}
void dfs_cnt(int now,int fa){
for(auto i:mp[now]){
if(i==fa||i==1)continue;
vistime.push_back(sz[i]*(sz[1]-sz[i]));
dfs_cnt(i,now);
}
}
int main() {
Turnoff;
int t;cin>>t;
while(t--){
int n;cin>>n;vistime.clear();
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
mp[u].push_back(v);
mp[v].push_back(u);
sz[i]=1;
}sz[n]=1;
int m;cin>>m;
vector<ll>prime;
for(int i=0;i<m;i++){
int p;cin>>p;
prime.push_back(p);
}
sort(prime.begin(),prime.end(),greater<ll>());
dfs_size(1,0);
dfs_cnt(1,0);
sort(vistime.begin(),vistime.end(),greater<ll>());
int pos=0,mm=m;
while(mm>n-1&&pos+1<m){
prime[pos+1]=((prime[pos+1]%Mod)*(prime[pos]%Mod))%Mod;
mm--;pos++;
}
ll sum=0;
for(auto i:vistime){
ll temp=pos<m?prime[pos]:1;
sum=(sum%Mod+((i%Mod)*(temp%Mod))%Mod)%Mod;pos++;
}
cout<<sum<<endl;
for(int i=1;i<=n;i++)mp[i].clear();
}
}
|