Div2 D WA #5 求助
  • 板块学术版
  • 楼主wurzang
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/8/22 00:42
  • 上次更新2023/11/6 19:42:25
查看原帖
Div2 D WA #5 求助
344016
wurzang楼主2020/8/22 00:42
#include<bits/stdc++.h>
using namespace std;
int rd(){
	int x=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x;
}
typedef long long ll;
const ll mod=1e9+7;
const int N=100000+5;
vector<int> e[N];
int n,tot,sz[N];ll cnt[N];
void dfs(int x,int fath){
	sz[x]=1;
	for(int i=0;i<e[x].size();++i)
		if(e[x][i]!=fath){
			int v=e[x][i];
			dfs(v,x);
			sz[x]+=sz[v];
			cnt[++tot]=1ll*sz[v]*(n-sz[v]);
		}
}
bool cmp(int i,int j){return i>j;}
ll p[N];
int main(){
	int m,t,u,v;
	ll ans=0;
	t=rd();
	while(t--){
		n=rd();
		for(int i=1;i<=n;++i)
			e[i].clear();
		for(int i=1;i<n;++i){
			u=rd();v=rd();
			e[u].push_back(v);
			e[v].push_back(u);
		}
		tot=0;
		dfs(1,0);
		sort(cnt+1,cnt+tot+1,cmp);
		for(int i=1;i<=tot;++i) cnt[i]%=mod;
		m=rd();
		for(int i=1;i<=m;++i)
			p[i]=rd();
		sort(p+1,p+m+1);
		while(m>tot)
			p[m-1]=p[m-1]*p[m]%mod,--m; 
		//for(int i=1;i<=m;++i)cout<<p[i]<<" ";cout<<endl;
		ans=0;
		for(int i=1;i<=min(m,tot);++i)
			ans+=1ll*cnt[i]*p[m-i+1]%mod,ans%=mod;
		for(int i=m+1;i<=tot;++i)
			ans+=cnt[i],ans%=mod;
		cout<<ans<<endl;
	}
	return 0;
}

因为代码很容易看懂就不讲思路了。。。

2020/8/22 00:42
加载中...