题目链接
翻译
让你给树上的每条边分配一个数字。要求这 (n-1) 个数的乘积要等于 (k)
分配的 (1) 的个数要尽可能少。
这个 (k) 质因数分解的时候，每个质因子的指数都是 (1)，且 (k) 是以告诉你它每个质因子的形式给出的。
要求树上任意两点之间的距离和最大。输出这个最大值。
题解
感觉证明做法的正确性会比做法本身难。。
首先解决两点之间距离和这个问题。
可以转换成求树上的所有边，每条边的两边有多少条路径会经过这条边。(也即这条边对最后的路径和的贡献)
有几条路径 (cnt[i]) 会经过这条边 (i)，这条边的权值就要乘上几。
这样，答案就呼之欲出了。我们只要把大的质因子分配到那些 (cnt) 大的边上就可以了。
但是会出现 (m>n-1) 的情况，对于这种情况，把最大的 (m-(n-1)) 个质因子，乘起来，然后再和第 (m-(n-1)+1) 大的质因子乘一下就好。
这样就又变成 (n-1) 个权值待分配了。
而对于 (mlt n-1) 的情况，不足的部分只能用 (1) 补了(没办法避免用这些 (1),所以数目肯定是最少的)
代码
#include <bits/stdc++.h>
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
#define LL long long
using namespace std;
const int N = 1e5;
const LL MOD = 1e9+7;
LL p[N+10],dp[N+10],cnt[N*2+10];
int fir[N+10],nex[N*2+10],en[N*2+10],totm,n,m;
void add(int x,int y){
totm++;
nex[totm] = fir[x];
fir[x] = totm;
en[totm] = y;
}
void dfs(int x,int fa){
dp[x] = 1;
for (int i = fir[x];i>0;i = nex[i]){
int y = en[i];
if (y == fa){
continue;
}
dfs(y,x);
dp[x] += dp[y];
cnt[i] = 1LL*(n-dp[y])*dp[y];
}
}
int main(){
// freopen("C://1.cppSourceProgram//rush.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0);
int T;
cin >> T;
while (T--){
memset(cnt,0,sizeof(cnt));
totm = 0;
for (int i = 1;i <= n; i++){
fir[i] = 0;
}
cin >> n;
for (int i = 1;i <= n - 1; i++){
int x,y;
cin >> x >> y;
add(x,y);
add(y,x);
}
dfs(1,-1);
sort(cnt+1,cnt+1+totm);
reverse(cnt+1,cnt+1+totm);
//从大到小,只有前n-1条边的cnt>0
totm = n-1;
cin >> m;
for (int i = 1;i <= m; i++){
cin >> p[i];
}
sort(p+1,p+1+m);
reverse(p+1,p+1+m);
if (m <= n-1){
//从大到小安排
LL ans = 0;
for (int i = 1;i <= m; i++){
ans = ans + p[i]*cnt[i]%MOD;
ans%=MOD;
}
//剩余的全是 1
for (int i = m+1;i <= n-1; i++){
ans = ans + 1*cnt[i];
ans%=MOD;
}
cout << ans << endl;
}else{
//如果给的因子数目太多了。。就把最高的 m-(n-1)个合成一个。
for (int i = 1;i <= m-(n-1);i++){
p[m-(n-1)+1] = p[m-(n-1)+1]*p[i]%MOD;
}
LL ans = 0;
for (int i = m-(n-1)+1,j = 1; i <= m; i++,j++){
ans = ans + p[i]*cnt[j]%MOD;
ans%=MOD;
}
cout << ans << endl;
}
}
return 0;
}