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
using namespace std;
const int N = 2e5+10;
int n,m,k,T;
vector 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