题目链接

解题思路

对于每一条边，其贡献为断开它后两部分的siz的乘积乘以边权。所以我们对于每一个siz的乘积排序，对p排序，小的对小的，大的对大的，最大的将剩下所有全拿走即可。
其中siz在树上DFS求

代码

#include<bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
const int inf=1e9+7;
int t;
int head[200005];
int p[200005];
struct e{
    int to,nxt;
}edge[400005];
int tot=0;
long long ctr[200005];
void add_edge(int u,int v){
    tot++;
    edge[tot].nxt=head[u];
    edge[tot].to=v;
    head[u]=tot;
}
long long siz[200005];
void DFS(int now,int father){
    int nxtt;
    siz[now]=1;
    for(int i=head[now];i;i=edge[i].nxt){
        nxtt=edge[i].to;
        if(nxtt==father)continue;
        DFS(nxtt,now);
        siz[now]+=siz[nxtt];
    }
    return ;
}
long long n;
int main(){
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        tot=0;
        for(int i=1;i<=n;i++){
            head[i]=0,siz[i]=0,ctr[i]=0;
        }
        scanf("%lld",&n);
        int u,v;
        for(int i=1;i<=n-1;i++){
            scanf("%d%d",&u,&v);
            add_edge(u,v);
            add_edge(v,u);
        }
        DFS(1,0);
        int m;
        scanf("%d",&m);
        for(int i=1;i<=m;i++){
            scanf("%d",&p[i]);
        }
        for(int i=1;i<=n;i++){
            ctr[i]=siz[i]*(n-siz[i]);
        }
        sort(ctr+1,ctr+1+n);
        sort(p+1,p+1+m);
        //注意！！！切不可在sort前取摸 
        for(int i=1;i<=n;i++)ctr[i]%=Mod;  
        long long ans=0;
        if(m>=n){
            for(int i=2;i<=n-1;i++){
                ans+=ctr[i]*p[i-1];
                ans%=Mod;
            }
            long long mcon=1;
            for(int i=n-1;i<=m;i++){
                mcon*=p[i];
                mcon%=Mod;
            }
            ans+=ctr[n]%Mod*mcon%Mod;
            ans%=Mod;
            printf("%lld\n",ans);
        }else{
            int arr=m;
            for(int i=n;i>=2;i--){
                if(arr>0){
                    ans+=ctr[i]*p[arr];
                    arr--;
                    ans%=Mod;
                }else{
                    ans+=ctr[i];
                    ans%=Mod;
                }
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
} 

本文链接：http://kaispace.com.cn/index.php/archives/702/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者