Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree
19429 ワード
考点:図論、数論.
#include
#include
#include
#include
using namespace std;
const int maxn = 100010;
const long long mod = 1e9+7;
long long p[maxn];
vector<long long> v[maxn];
long long vis[maxn] = {0};
long long sum[maxn] = {0};
long long b[maxn];
void dfs(long long x){
sum[x]++;
for(long long i = 0;i<v[x].size() ;i++){
long long y = v[x][i];
if(vis[y]) continue;
vis[y] = 1;
dfs(y);
sum[x] += sum[y];
}
}
int main(){
long long t;
cin >> t;
while(t--){
long long n;
cin >> n;
memset(vis,0,sizeof(long long)*(n+10));
memset(sum,0,sizeof(long long)*(n+10));
long long s,t;
for(long long i = 0;i<n-1;i++){
cin >> s >> t;
v[s].push_back(t);
v[t].push_back(s);
}
vis[1] = 1;
dfs(1);
long long tt = 0;
for(long long i = 0;i<n;i++){
long long x = i+1;;
if(sum[x] == n) continue;
b[tt++] = (n-sum[x])*sum[x]%mod;
}
sort(b,b+n-1);
long long m;
cin >> m;
long long sum = 0;
for(long long i = 0;i<m;i++){
cin >> p[i];
}
sort(p,p+m);
if(m<n-1){
long long u = n-1-m;
for(long long i = m-1;i >= 0;i--){
p[i+u] = p[i];
}
for(long long i = 0;i<u;i++){
p[i] = 1;
}
}
else {
long long u = m-n+1;
for(long long i = m-1;i >= m-u;i--){
p[m-u-1] = (p[m-u-1]*p[i])%mod;
}
}
long long ans = 0;
for(long long i = 0;i<n-1;i++){
ans = (ans+b[i]*p[i]%mod)%mod;
}
cout << (ans%mod+mod)%mod << endl;
for(long long i = 1;i <= n;i++){
v[i].clear() ;
}
}
return 0;
}