CF1336 A. Linova and Kingdom

A. Linova and Kingdom

题意

给你一颗nnn个节点根为1号节点的树,选kkk个城市作为工业城市,其余为旅游城市,工业城市的使节每经过旅游城市开心值+1,求所有工业城市的使节到1号节点的开心值的和最大为多少?

思路

贪心 dfs
CF1336 A. Linova and Kingdom
很容易看出来如果只选一个,一定选距离根节点最远的叶子,我们思考第四个为什么选2而不是3和4,因为选3和4,会减少其子树节点的开心值。(因为我们选这个点,根据贪心我们肯定已经选了所有他子树的节点)
=每个结点的贡献值=到根节点的距离-子树的节点数每个结点的贡献值=到根节点的距离−子树的节点数
我们求出每个节点的贡献值,排序取最大的k个数即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

ll n,k,f[N],s[N];
vector<int>G[N];

void dfs(int x,int fa,ll d){
	f[x]=d;
	s[x]=1;
	for(int c:G[x]){
		if(c==fa) continue;
		dfs(c,x,d+1);
		s[x]+=s[c];
		f[x]-=s[c];
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,-1,0);
	sort(f+1,f+1+n,greater<ll>());
	ll res=0;
	for(int i=1;i<=k;i++){
		res+=f[i];
	}
	cout<<res<<'\n';
	return 0;
}
上一篇:Linova and Kingdom


下一篇:Codeforces 1337C Linova and Kingdom