A. Linova and Kingdom

题目大意：给定n个城市，其中有k个工业城市，n-k个旅游城市，求从所有工业城市到首都（1）的过程中经过的旅游城市之和的最大值。

题解：

1，根据贪心的策略，工业城市与旅游城市的父子关系是确定的，旅游城市为父亲结点而工业城市为儿子结点。（可以利用反证法证明）

2，基于结论1，我们可以定义每一个点的权重为：该点到1的距离-该点的子节点个数，然后我们选择k个最大的结点即可。

注意答案要开long long 

#include
using namespace std;
const int maxn = 2e5 + 10;
vectorg[maxn];
int fa[maxn];
int dep[maxn];
int son[maxn];
int val[maxn];
void dfs(int x,int deep)
{
	val[x] = deep;
	son[x] = 1;
	for (int i = 0; i < g[x].size(); i++)
	{
		if (fa[x] != g[x][i])
		{
			son[x] += (son[g[x][i]]);
			fa[g[x][i]] = x;
			dfs(g[x][i], deep + 1);
			son[x] += son[g[x][i]];
			val[x] -= son[g[x][i]];
		}
	}
	
}
int main()
{
	int n, k;
	cin >> n >> k;
	int x, y;
	for (int i = 1; i <= n - 1; i++)
	{
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dep[1] = 0;
	fa[1] = 1;
	dfs(1, 0);
	sort(val + 1, val + 1 + n);
	long long ans = 0;
	for (int i = n; i >= n - k + 1; i--)
	{
		ans += val[i] ;
	}
	cout << ans;
}