警示后人Wa on #2
查看原帖
警示后人Wa on #2
569878
C201529楼主2024/8/8 20:00
#include<stdio.h>
#include<list>
#include<algorithm>
#define mod 1000000007
#define endl putchar('\n')
#define F(i,l,r) for(ll i=l;i r;++i)
#define R(i,r,l) for(ll i=r;i l;--i)
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
typedef long long ll;
typedef unsigned long long u64;
//typedef std::pair<ll,ll> _2;
//char *p1,*p2,buf[300000];
//#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,300000,stdin),p1==p2)?EOF:*p1++)
long long readzy;short readzyf;char readc;
char isdig() {
	return readc>47&&readc<58;
}
long long read() {
	readzy=0;
	readzyf=1;
	readc=getchar();
	for (; !isdig(); readc=getchar())if (readc=='-')readzyf=-1;
	for (; isdig(); readc=getchar())
		readzy =(readzy<<1)+(readzy<<3)+(readc^48);
	return readzy*readzyf;
}
std::list<int> lis[100033];
int n,m,t1,t2,T,a[60033],size[100033];
ll w[100033],ans;
int dfs(int x,int f){
	size[x]=1;
	for(auto i:lis[x]){
		if(i==f)continue;
		size[x]+=dfs(i,x);
	}
	w[x]=1ll*size[x]*(n-size[x]);
	return size[x];
}
bool cmp1(int a,int b){return a>b;}
int main(){
//	file("");
	T=read();
	while(T--){
	n=read();ans=0;
	F(i,1,<=n)lis[i].clear();
	F(i,1,<n){
		t1=read();t2=read();
		lis[t1].push_back(t2);
		lis[t2].push_back(t1);
	}
	m=read();
	F(i,1,<=m)a[i]=read();
	dfs(n,0);
	std::sort(w+1,w+n,cmp1);
	std::sort(a+1,a+m+1,cmp1);
//	F(i,1,<n)printf("%lld ",w[i]);endl;
//	F(i,1,<=m)printf("%lld ",a[i]);endl;
	if(m<n){
		F(i,1,<=m)ans=(ans+w[i]*a[i]%mod)%mod;
		F(i,m+1,<n)ans=(ans+w[i])%mod;
	}
	else{
		F(i,2,<n)ans=(ans+w[i]*a[m-n+1+i]%mod)%mod;
		F(i,2,<=m-n+2)a[1]=a[1]*a[i]%mod;
//		printf("%lld\n",w[1]*a[1]);
		ans=(ans+w[1]*a[1]%mod)%mod;
	}
	printf("%lld\n",ans);
	}
	return 0;
}
/*Long live Kickey!
Miss you all the time.*/

bool cmp1(int a,int b){return a>b;}

bool cmp1(ll a,ll b){return a>b;}

F(i,2,<=m-n+2)a[1]=a[1]*a[i]%mod;

F(i,2,<=m-n+2)a[1]=1ll*a[1]*a[i]%mod;

sort的cmp一定要开long long

2024/8/8 20:00
加载中...