Solution. CF1336A Linova and Kingdom

出作了模拟赛的 T2，实际上为 T1 难度。

Description

一棵 $n$ 个点，以 $1$ 为根的有根数，其中 $k$ 个点标记为 A 类，其余点标记为 B 类。

A 类点 $u$ 的权值定义为 $u\to 1$ 路径上 B 类点的数量。

最大化 A 类点的权值和。

$n\le 2\times 10^5$

Solution

Observation：一个点被标记为 A 类，则其子树中所有点均为 A 类点。

证明非常简单，考虑若 $u$ 被标记为 A 类，其子树中存在一个点 $v$ 被标记为 B 类，那么我们交换 $u,v$，答案一定会变优。

令一个点为 A 类点会使得子树内所有 A 类点的对答案的贡献 -1。

于是不难想到令每个点的权值为 $dep_u-siz_u$，按照权值从大到小进行贪心。

这样贪心不会存在选了一个点但没有选某一个子孙的情况，因为子孙的权值一定比当前点大，于是贪心的正确性就能够保障了。

Code

namespace Main{
    const int N = 200005;
    int n, k, a[N], dep[N], siz[N];
    ll ans;
    vector<int> g[N];
    void dfs(int u, int fa){
        dep[u] = dep[fa] + 1;
        siz[u] = 1;
        for(ri i = 0; i < g[u].size(); i++){
            int v = g[u][i];
            if(v == fa) continue;
            dfs(v, u);
            siz[u] += siz[v];
        }
    }
    void Main(){
        input(n, k);
        for(ri i = 1, u, v; i < n; i++){
            input(u, v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, 0);
        for(ri i = 1; i <= n; i++) a[i] = i;
        sort(a + 1, a + n + 1, [](int x, int y){
            return dep[x] - siz[x] > dep[y] - siz[y];
        });
        for(ri i = 1; i <= k; i++) ans += dep[a[i]] - siz[a[i]];
        write(ans);
        return;
    }
} // namespace

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。