codeforces Linova and Kingdom

题目
题意: 给定以1为根的树，选择恰好k个点染黑色，其余点为白色。这k个点的幸福值为其到树根的最短路上白色点的个数，问和最大为多少。
思路: 贪心。首先深度深的叶子最优，其次就不好说了，选了父节点子节点贡献就会减少。不妨把子节点贡献减少的值交给父节点，这样总和不变，可以据此直接排序选出贡献最大的k个点。
时间复杂度: O(nlogn)
代码:

// Problem: A. Linova and Kingdom
// Contest: Codeforces - Codeforces Round #635 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1336/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n,m,k,T;
vector<int> va[N];
int sz[N];
int ans[N];
void dfs(int cur,int fa,int d)
{
    
	sz[cur] = 1;
	for(auto j:va[cur])
	{
    
		if(j==fa) continue;
		dfs(j,cur,d+1);
		sz[cur] += sz[j];
	}
	// if(cur==4) cout<<d<<" "<<sz[cur]<<"\n";
	ans[cur] = d - sz[cur] + 1;
}
void solve()
{
    
	cin>>n>>k;
	for(int i=0;i<n-1;++i)
	{
    
		int x,y; cin>>x>>y;
		va[x].push_back(y),va[y].push_back(x);
	}
	dfs(1,0,0);
	// for(int i=1;i<=n;++i) cout<<i<<":"<<ans[i]<<"\n";
	sort(ans+1,ans+n+1);
	int now = n;
	long long res = 0;
	while(k--)
	{
    
		res += ans[now--];
	}
	cout<<res;
}
signed main(void)
{
    
	solve();
	return 0;
}