题目链接
题目大意
有一棵树 一共有n-1边 你需要给n-1边赋值 需要满足以下条件
1每个值大于0正整数
2所有值的1的数量最少
3所有值的乘积为k （k给出 k的素因数们也给出）
在满足以上条件的基础上
要求这个 
值最大 ，f（u,v）代表是u和v之间的简单路径
题目思路
题目可转化为求每个边所经过的次数 然后进行贪心将pi值填进去
问题主要在于在这个公式下
如何求树上每个边经过的次数
在这个公式下任意两个点都有一次将两点之间的简单路径逐个次数++的运算
那么对于每一条边(u,v)的经过次数 只需要计算 这个边左节点的节点数量*右节点的节点数量
即sz[u]*sz[v]=sz[u]*(n-sz[u])
对于sz的计算用一次dfs即可 方式类似于求树深度和直径之类的
最后注意贪心
判断一下m与n-1数量关系
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
const int maxm=2e5+10;
const int mod=1e9+7;
int t,n,m;
int cnt=1;
int tot=0;
ll head[maxn*2];
ll p[maxn];
ll a[maxn];
ll sz[maxn*2];
struct xy
{ll next,to,dis;
}e[maxm*2];
void add(int u,int v,ll d)
{e[++cnt].dis=d;e[cnt].next=head[u];e[cnt].to=v;head[u]=cnt;
}
void init()
{cnt=1;tot=0;memset(head,0,sizeof(head));memset(e,0,sizeof(e));for(int i=0;i<=n;i++) {sz[i]=0;a[i]=0;p[i]=0;}
}
bool cmp(ll x,ll y)
{if(x>y)return 1;else return 0;
}
void dfs(int now,int fa)
{int u=now;sz[u]=1;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==fa)continue;dfs(v,u);sz[u]+=sz[v];a[++tot]=sz[v]*(n-sz[v]);}
}
int main()
{cin>>t;while(t--){cin>>n;init();int x,y;for(int i=1;i<=n-1;i++){cin>>x>>y;add(x,y,1);add(y,x,1);}dfs(1,0);cin>>m;for(int i=1;i<=m;i++){cin>>p[i];} sort(a+1,a+tot+1,cmp);sort(p+1,p+m+1,cmp);ll ans=0;if(m<=n-1){for(int i=1;i<=tot;i++){if(i<=m){ans=(ans+(p[i]%mod*a[i]%mod)%mod)%mod;}else {ans=(ans+a[i]%mod)%mod;}}}else {ll pos=1;for(int i=1;i<=m-n+2;i++){pos=(pos*p[i]%mod)%mod;//ans=(ans+(a[1]%mod*p[i]%mod)%mod)%mod;}ans=a[1]*pos%mod;ans%mod;for(int i=2;i<=tot;i++){ans=(ans+(a[i]%mod*p[m-n+i+1]%mod)%mod)%mod;}}cout<<ans%mod<<endl;}return 0;
}