题解：P6574 [BalticOI 2017] Cat in a tree

· · 题解

一道贪心加线段树题。

题意

在树上标记点，任意两点的简单距离不小于 d，求最多能标记多少个点。

贪心思路

我们定义，对于一个被标记的点，称与其简单距离小于 d 的点为被其覆盖的点。贪心思路为每一次找未被覆盖的点中的最深的点标记。

证明

在未被覆盖的点中，对于一个的点 v，若选了他会覆盖最深点 u，那么选 u 所覆盖的点一定包含于选 v 所覆盖的点，所以选 u 一定优于选 v。

如何覆盖

如果我们每选一个点都去暴力覆盖其他点，会超时。考虑用线段树维护一个点是否被覆盖。我们定义 deep(a) 表示 a 点的深度。对于被标记的点 u，找其祖先 v，我们要覆盖以 v 为根，深 d-(deep(v)-deep(u))-1 的树。但是，线段树只能一下处理一整棵子树，这要怎么办呢？我们发现，我们找点是由深到浅找的，所以如果我们要处理一棵根为 x，最深深度为 y 的子树时，等到找点找到深度 y 的时候再用线段树更新整棵以 x 为根的子树即可。

时间复杂度

判断是否被覆盖：O(n \log{n})。

覆盖：O(ans \times d \times \log{n})。又因为 ans \times d \le n，所以复杂度实际上为 O(n \log{n})。

总复杂度：O(n \log{n})。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,k,c,d[200005],ans,dfs[200005],dfss,s[200005],fa[200005],t[800005];
vector<int> a[200005];//邻接表
struct xxx
{
    int x,y;
    bool operator < (const xxx o) const{return y<o.y;}
    bool operator > (const xxx o) const{return y>o.y;}
};
priority_queue<xxx> f,p;
//p存的是覆盖以x为根，最大深度为y的树的操作
void dfs1(int x)
{
    dfs[x]=++dfss;//dfs序
    s[x]=1;//子树大小
    f.push((xxx){x,d[x]});
    for(int i=0;i<a[x].size();i++)
    if(a[x][i]!=fa[x])
    {
        int y=a[x][i];
        d[y]=d[x]+1;//深度
        fa[y]=x;//父亲节点
        dfs1(y);
        s[x]+=s[y];
    }
}
void update(int num,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        t[num]=1;
        return;
    }
    if(x>r||y<l)
    return;
    update(num*2,l,(l+r)/2,x,y);
    update(num*2+1,(l+r)/2+1,r,x,y);
}
bool query(int num,int l,int r,int x)
{
    if(t[num]==1)
    return false;
    if(l==r)
    return true;
    if(x<=(l+r)/2)
    return query(num*2,l,(l+r)/2,x);
    else
    return query(num*2+1,(l+r)/2+1,r,x);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;//k即题目中的d
    for(int i=2;i<=n;i++)
    {
        cin>>c;
        //这里给每一个点的编号都加了1，方便处理
        c++;
        a[c].push_back(i);
        a[i].push_back(c);
    }
    dfs1(1);
    while(!f.empty())
    {
        int x=f.top().x;
        f.pop();
        ans++;
        p.push((xxx){x,d[x]+k-1});
        while(!f.empty())//判断堆头的点是否被覆盖
        {
            while(!p.empty()&&p.top().y>=d[f.top().x])
            {
                while(p.top().y>d[f.top().x]+1)//小优化（对于影响过深的点）
                {
                    p.push((xxx){fa[p.top().x],p.top().y-2});
                    p.pop();
                }
                if(d[p.top().x]>p.top().y)
                {
                    p.pop();
                    continue;
                }
                if(p.top().x==0)//跳过头了，说明所有点都被覆盖
                {
                    update(1,1,n,1,n);
                    while(!p.empty())
                    p.pop();
                    break;
                }
                update(1,1,n,dfs[p.top().x],dfs[p.top().x]+s[p.top().x]-1);
                p.push((xxx){fa[p.top().x],p.top().y-2});
                p.pop();
            }
            if(query(1,1,n,dfs[f.top().x]))
            break;
            else
            f.pop();
        }
    }
    cout<<ans;
}