洛谷CF1336A Linova and Kingdom 题解

题意：

给定 \(n\) 个节点的有根树，根是 \(1\) 号节点。

你可以选择 \(k\) 个节点将其设置为工业城市，其余设置为旅游城市。

对于一个工业城市，定义它的幸福值为工业城市到根的路径经过的旅游城市的数量。

你需要求出所有工业城市的幸福值之和的最大可能值。

输入格式：

The first line contains two integers \(n\) and \(k\) ( \(2\le n\le 2 \times 10^5\) , \(1\le k< n\) ) — the number of cities and industry cities respectively.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) ( \(1\le u,v\le n\) ), denoting there is a road connecting city \(u\) and city \(v\) .

It is guaranteed that from any city, you can reach any other city by the roads.

输出格式：

Print the only line containing a single integer — the maximum possible sum of happinesses of all envoys.

提示：

In the first example, Linova can choose cities \(2\) , \(5\) , \(6\) , \(7\) to develop industry, then the happiness of the envoy from city \(2\) is \(1\) , the happiness of envoys from cities \(5\) , \(6\) , \(7\) is \(2\) . The sum of happinesses is \(7\) , and it can be proved to be the maximum one.

结论：最优方案中，一个节点作为工业城市的充要条件是，这个节点所在子树的其他节点均已作为工业城市。

证明：

必要性证明：

若存在一个工业城市 \(x\) 的子孙 \(y\) 为旅游城市，

那么将 \(x\) 和 \(y\) 的类型交换后，\(y\) 子树的所有节点贡献不变，且其余属于 \(x\) 子树的节点贡献加 \(1\) 。
充分性证明：

考虑贪心。根据必要性可知我们一定是从下往上去选的。

考虑一个节点 \(u\) 的贡献，为 \(\mathtt{dep}(u) - \mathtt{size}(u)-1\) 。

其中 \(-\mathtt{size}(u)\) 是因为选了 \(u\) 以后， \(u\) 所在子树每个结点都会少 \(1\) 个旅游景点。

然后我们直接按贡献排序选前 \(k\) 大即可。下面我们说明这个做法满足充分性。

因为对于任意节点 \(x,y\) （ \(x\) 为父亲，\(y\) 为子结点）有 \[ \mathtt{size}(y) < \mathtt{size}(x) \\\mathtt{dep}(y) = \mathtt{dep}(x) + 1 > \mathtt{dep}(x) \] 则有 \(\mathtt{dep}(y) - \mathtt{size}(y) - 1 > \mathtt{dep}(x) - \mathtt{size}(x) - 1\) ，则 \(y\) 会先被选。

故正确性得证。\(\square\)

接下来就是实现的问题了。

我们可以用 nth_element + greater<int>() 来求解前 \(k\) 大值。

虽然只有第 \(k\) 个元素放对了位置，但是 \(k\) 前面的元素都大于 \(k\) ，因此对于前 \(k\) 大值的和可以直接算

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+15))

int n,k,pos = 1,head[N],a[N],sz[N],dep[N];
struct Edge { int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void dfs(int u,int fa)
{
    dep[u] = dep[fa] + 1; sz[u] = 1;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v; if(v == fa) continue;
        dfs(v,u); sz[u] += sz[v];
    }
    a[u] = dep[u] - sz[u];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k;
    for(int i=1,u,v; i<n; i++)
    {
        cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }
    dfs(1,0);
    nth_element(a + 1, a + k, a + 1 + n, greater<int>());
    int res = 0; for(int i=1; i<=k; i++) res += a[i];
    cout << res << '\n';
    return 0;
}