【*1800树上贪心】CF1401 D

桃扇骨 2024-03-22 21:13 95阅读 0赞

[Problem - D - Codeforces][]

题意：

![7241a05d87fd42e4a44bf4eefee86eac.png][]

![f4ea9d3e03d1451e84933f771f16b79f.png][]

思路：

首先，1尽可能少，那就是让pi尽可能不合并地摊到所有边上，然后计算贡献

按照CF惯用套路，这样的n^2贡献肯定是更换枚举对象，我们去枚举边，按边算贡献

对于一条边的贡献应该为sz\[u\]\*(N-sz\[u\])\*p\[i\]

然后就是贪心了，大的边权摊到经过次数多的边，小边权到次数小的边

同时需要分类讨论这些给定的质因子个数和边数的大小关系

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mod=1e9+7;
    
    array<int,3> E[mxn];
    
    vector<int> G[mxn];
    
    int N,M;
    int u[mxn],v[mxn];
    int dep[mxn],sz[mxn],p[mxn],v2[mxn];
    
    void dfs(int u,int fa){
    	sz[u]=1;
    	dep[u]=dep[fa]+1;
    	for(auto v:G[u]){
    		if(v==fa) continue;
    		dfs(v,u);
    		sz[u]+=sz[v];
    	}
    }
    bool cmp(int x,int y){
    	return x<y;
    }
    bool cmp2(array<int,3> x,array<int,3> y){
    	return x[0]<y[0];
    }
    void init(){
    	for(int i=0;i<=N;i++){
    		G[i].clear();
    		dep[i]=sz[i]=0;
    	}
    }
    void solve(){
    	cin>>N;
    	init();
    	for(int i=1;i<=N-1;i++){
    		cin>>u[i]>>v[i];
    		G[u[i]].push_back(v[i]);
    		G[v[i]].push_back(u[i]);
    	}
    	dfs(1,0);
    	for(int i=1;i<=N-1;i++){
    		if(dep[u[i]]<dep[v[i]]) swap(u[i],v[i]);
    		E[i]={sz[u[i]]*(N-sz[u[i]]),u[i],v[i]};
    	}
    	sort(E+1,E+1+N-1,cmp2);
    	cin>>M;
    	for(int i=1;i<=M;i++) cin>>p[i];
    	sort(p+1,p+1+M,cmp);
    	int ans=0;
    	/*if(N-1>=M+1){
    		for(int i=M+1;i<=N-1;i++) p[i]=1;
    		for(int i=1;i<=N-1;i++){
    			ans+=E[i][0]*p[i];
    			ans%=mod;
    		}
    	}else{
    		for(int i=1;i<=N-1;i++) ans+=E[i][0]*p[i]%mod,ans%=mod;
    		for(int i=N;i<=M;i++) ans+=E[1][0]*p[i]%mod,ans%=mod;
    	}
    	cout<<ans%mod<<'\n';*/
    	N --;
    		
    		if (M <= N) {
    			for (int i = 1; i <= N - M; i ++) v2[i] = 1;
    			for (int i = N - M + 1; i <= N; i ++) v2[i] = p[i - (N - M)];
    		}
    		else {
    			v2[N] = 1;
    			for (int i = 1; i < N; i ++) v2[i] = p[i];
    			for (int i = N; i <= M; i ++) v2[N] = v2[N] * p[i] % mod;
    		}
    		
    		for (int i = 1; i <= N; i ++) ans = (ans + E[i][0] % mod * v2[i] % mod) % mod;
    		
    		printf("%lld\n", ans);
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1401/problem/D
[7241a05d87fd42e4a44bf4eefee86eac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/90a93c64a3894b948d653e11a1368e55.png
[f4ea9d3e03d1451e84933f771f16b79f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/5793f0bc8412420b9a455d5d63359d58.png