洛谷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;
}