【题解】CF1336A Linova and Kingdom

· · 题解

分析 + 题解

看到一道跟树相关的题目，你想到了什么？树形 DP？dfs 序？还是树剖？

我相信，当你读完题面和样例解释后，你一定会说：“都不是，这只是个贪心罢了。”

没错，一种显然的贪心策略是（从下往上）选择深度尽量大、子树大小尽量小的节点，但这不完全正确，因为你没有求得这两个属性在最优性中的权重，下面将进行推导。

首先给出一个显然正确的结论：将一个节点作为工业城市的必要不充分条件是，这个节点所在子树的其他节点均已作为工业城市。

证明：若存在一个工业城市 x 的子孙 y 为旅游城市，那么将 x 和 y 的类型交换后，y 子树的所有节点贡献不变，且其余属于 x 子树的节点贡献加 1。

这启发我们一件事：点 x 从旅游城市变为工业城市的贡献为 dep_x-sz_x，其中 dep_i 表示 i 号点的深度（dep_1=1），sz_i 表示以 i 为根子树的大小。

说明：此时，x 新增贡献 dep_x，且 x 子树内所有节点贡献减 1（包括 x，即 x 的当前贡献为 dep_x-1）。

因此，我们只需贪心选取 dep_x-sz_x 前 k 大的 x 节点作为工业城市即可。

有人可能会问，需不需要考虑上文提到的必要条件。答案是否定的，因为对于任意父子关系 x 和 y（x 是 y 的父亲），显然有 dep_y=dep_x+1>dep_x，sz_y<sz_x，进一步有 dep_y-sz_y>dep_x-sz_x。也就是说，根据这种贪心策略选取，必定满足“先选子孙，再选自己”。

代码实现

只需遍历一遍树，计算出 dep 和 sz，并使用 nth_element() 求得 dep-sz 的前 k 大，将其求和即为答案。

时间复杂度：O(n)

轻轻松松最优解^_^

补充：有关 STL 中的 nth_element()

作用：求区间第 k 小，并将比这个数小的数放在它之前，将比它大的放在它之后（无序，但足以求区间前 k 小）。

用法：前三个参数分别为起始位置，第 k 个元素所在位置，结束位置（左闭右开），第四个参数为比较函数（可省略，默认为 <）。

时间复杂度：O(len)，len 为区间长度。（类似快速排序实现）

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=2e5+5;
int End[max_n<<1],Last[max_n],Next[max_n<<1],e;
inline void add_edge(int x,int y)
{
    End[++e]=y;
    Next[e]=Last[x];
    Last[x]=e;
    End[++e]=x;
    Next[e]=Last[y];
    Last[y]=e;
}
int dep[max_n],sz[max_n],val[max_n];
void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;
    sz[x]=1;
    for(int i=Last[x];i;i=Next[i])
    {
        int y=End[i];
        if(y!=fa)
        {
            dfs(y,x);
            sz[x]+=sz[y];
        }
    }
    val[x]=dep[x]-sz[x];
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n-1;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add_edge(u,v);
    }
    dfs(1,0);
    nth_element(val+1,val+k,val+n+1,greater<int>());//看似求第 k 大，实则获得前 k 大 
    long long ans=0;
    for(int i=1;i<=k;++i)
        ans+=val[i];
    printf("%lld\n",ans);
    return 0;
}