Codeforces Round #635 (Div. 2).C题

C.

/* 题目C： 给一颗树，现在你可以将K个节点染成白色，并将其余节点染成黑色，要求所有白色节点到节点1路径上经过黑色节点和最大 坑点：需要经过黑色节点而不是包含白色节点，因此光求深度是不够的      求总数时应该定义ll,会爆int */ #include <bits/stdc++.h> #define INT 0x7fffffff #define  cind(x) scanf("%d",&x) #define cinc(x) scanf("%c",&x);while(ch==' '||ch=='n')scanf("%c",&x); #define kt  int t;scanf("%d",&t);while(t--) #define mem0(x) memset(x,0,sizeof(x)); #define ll long long int #define mem(x,y) memset(x,y,sizeof(x)); const int inf = 200005; #define INT2 0x7ffffff #define scanf scanf_s using namespace std; int a[400005], b[400005]; set<int> s[200005]; int dep[200010];//表示该点距离根节点 int fencha[200010];//表示该点有没有分叉，用来判断其是不是最后一个节点 int hm[200010];//用来记录每个点后面的子节点数 int maxx = 0; int fun(int root, int t)//本题每个点的实际贡献就是该点距离根的深度减去该点的所有孩子,先用dfs求出每个点年的根深度以及孩子数量，再在主函数中将两个数组相减并且将结果降序排序，取前k个即可。 {  dep[root] = t + 1;  set<int>::iterator it; for (it = s[root].begin(); it != s[root].end(); it++) { if (b[*it] == 0) {    b[*it] = 1;    hm[root] += fun(*it, t + 1);    fencha[root]++; } } if (fencha[root] == 0) {   hm[root] = 0; } return hm[root] + 1; } bool cmp(int a, int b) { return a > b; } int main() { int t, n, i, j, k, m; int x, y, z;   cin >> n >> k;   b[1] = 1; for (i = 0; i < n-1; i++) {    cin >> x >> y;    s[x].insert(y);    s[y].insert(x); } fun(1, -1); for (i = 1; i <= n; i++) {    b[i] = dep[i] - hm[i]; } sort(b + 1, b + n + 1, cmp);   ll sum = 0; for (i = 1; i <= k; i++) {    sum += b[i]; }   cout << sum << endl; }