A. Linova and Kingdom
题意
给你一颗n个节点根为1号节点的树,选k个城市作为工业城市,其余为旅游城市,工业城市的使节每经过旅游城市开心值+1,求所有工业城市的使节到1号节点的开心值的和最大为多少?
思路
贪心 dfs
很容易看出来如果只选一个,一定选距离根节点最远的叶子,我们思考第四个为什么选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;
}