求救!!!RE80
查看原帖
求救!!!RE80
723954
yhyz2021017楼主2024/1/6 14:36
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+5,M=6e4+5,mod=1e9+7;
ll T,n,m,p[M],size[N];
vector<ll>g[N],v;
void dfs(ll x,ll fa) {
	size[x]=1;
	for(ll i=0;i<g[x].size();i++) {
		ll y=g[x][i];
		if(y==fa) continue;
		dfs(y,x);
		size[x]+=size[y];
		v.push_back(size[y]*(n-size[y]));
	}
}
int main() {
	scanf("%lld",&T);
	while(T--) {
		scanf("%lld",&n);
		for(ll i=1,u,v;i<n;i++) {
			scanf("%lld%lld",&u,&v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
		dfs(1,0);
	//	for(ll i=2;i<=n;i++) cout<<size[i]<<endl; 
		scanf("%lld",&m);
		for(ll i=1;i<=m;i++) scanf("%lld",&p[i]);
		if(m<=n-1) {
			for(ll i=m+1;i<n;i++) p[i]=1;
			sort(p+1,p+n);
		}else {
			sort(p+1,p+m+1);
			for(ll i=n;i<=m;i++) p[n-1]=1ll*p[n-1]*p[i]%mod;
		}
		sort(p+1,p+n);
		sort(v.begin(),v.end());
		ll ans=0;
		for(ll i=v.size()-1;i>=0;i--) ans=(ans+v[i]%mod*p[i+1])%mod;
		printf("%lld\n",ans);
		for(ll i=0;i<=n;i++) g[i].clear();
		v.clear();
		memset(p,0,sizeof p);
		memset(size,0,sizeof size);
	}
	return 0;
}
2024/1/6 14:36
加载中...