Linova and Kingdom

Linova and Kingdom

Linova and Kingdom 题目链接

思路

我们可以知道，如果把一座城市当成工业城市，它会影响其子树上的点，我们定义两个数组，一个dis代表当前节点到根节点1的距离，sz数组代表，当前节点的子树的节点数量。
通过贪心，也就是得到 \(dis - sz\) 的前 \(k\) 项。

再贪心之前我们必须得明白，选址工业城市一定是从外向内的，所以上面的贪心是一定成立的，当选了一个节点作为工业城市时，其子树上的所有节点一定也必须是工业城市了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N1 = 2e5 + 10, N2 = 4e5 + 10;
int head[N1], to[N2], nex[N2], cnt = 1;
int dis[N1], sz[N1], n, m;
void add(int x, int y) {
    to[cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt++;
}
void dfs(int now, int fa) {
    dis[now] = dis[fa] + 1;
    sz[now] = 1;
    for(int i = head[now]; i; i = nex[i]) {
        // cout << to[i] << endl;
        if(to[i] != fa) {
            dfs(to[i], now);
            sz[now] += sz[to[i]];
        }
    }
    dis[now] -= sz[now];
}
int main() {
    // freopen("in.txt", "r", stdin);
    int x, y;
    scanf("%d %d",&n, &m);
    for(int i = 1; i < n; i++) {
        scanf("%d %d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(1, 0);
    sort(dis + 1, dis + n + 1, greater<int> ());
    ll ans = 0;
    for(int i = 1; i <= m; i++)
        ans += dis[i];
    printf("%lld\n", ans);
    return 0;
}