欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-08-15 19:44:23
题目链接思路:dfs讨论m和n−1之间的大小关系,再计算每条边的贡献次数排序。代码:#include#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=998244353;const in...

题目链接

思路:

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

相关标签: dfs