Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree（dfs）

题目链接

思路：

dfs讨论m和n−1之间的大小关系，再计算每条边的贡献次数排序。

代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=2e5+7;
const int M=2e4+5;
const double eps=1e-8;
const int mod=1e9+7;
const int inf=0x7fffffff;
const double pi=3.1415926;
using namespace std;
vector<int>v[N],num;
int n;
int dfs(int x,int fa)
{
	int sum=1;
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==fa)
            continue;
		sum+=dfs(v[x][i],x);
	}
	if(x!=1)
		num.push_back((n-sum)*sum);
	return sum;
}
signed main()
{
    IOS;
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<=n;i++)
			v[i].clear();
		num.clear();
		for(int i=1;i<n;i++)
		{
			int x,y;
			cin>>x>>y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		int m;
		cin>>m;
		vector<int>p;
		for(int i=0;i<m;i++)
		{
			int c;
			cin>>c;
			p.push_back(c);
		}
		dfs(1,-1);
		if(m<n-1)
        {
            for(int i=0;i<n-1-m;i++)
                p.push_back(1);
        }
		sort(num.begin(),num.end());
		sort(p.begin(),p.end());
		int ans=0;
		if(m<=n-1)
		{
			for(int i=0;i<n-1;i++)
			{
				ans+=(num[i]*p[i])%mod;
				ans%=mod;
			}
		}
		else
		{
			for(int i=0;i<n-2;i++)
			{
				ans+=(num[i]*p[i])%mod;
				ans%=mod;
			}
			long long add=1;
			for(int i=n-2;i<m;i++)
            {
                add=(add*p[i])%mod;
            }

			ans+=(add*num[n-2])%mod;
			ans%=mod;
		}
		cout<<ans<<endl;
	}
	return 0;
}

本文地址：https://blog.csdn.net/ACkingdom/article/details/108178252