专栏文章

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

SSMHBD_
P6574题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mins9j3d
此快照首次捕获于
2025/12/02 07:31
3 个月前
此快照最后确认于
2025/12/02 07:31
3 个月前
查看原文
一道贪心加线段树题。

题意

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

贪心思路

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

证明

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

如何覆盖

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

时间复杂度

判断是否被覆盖：O(nlog⁡n)O(n \log{n})。
覆盖：O(ans×d×log⁡n)O(ans \times d \times \log{n})。又因为 ans×d≤nans \times d \le n，所以复杂度实际上为 O(nlog⁡n)O(n \log{n})。
总复杂度：O(nlog⁡n)O(n \log{n})。

代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...