【题解】[COCI2020] Pastiri

· · 题解

树上贪心神题

首先是和 这题 有一个相同的贪心策略，就是对于一个深度最深的点，选择他的最高祖宗一定比选择他的某个兄弟子树优。（因为它是深度最深的点，那么没有比它深的点，所以在其它子树一定不优，最高的祖宗是因为能看守到更多的羊）

然后我们可以预处理每一个点到最近的羊的距离，然后对羊从小到大排序，对每只羊暴力跳到最浅的祖宗，然后对于每个祖宗能覆盖到的羊标记一下。

这样做复杂度是对的是因为在标记时可以用 dis 判断子树内有没有能看管到的羊，在此之后走过的点就不会重复走了。这样均摊复杂度是 O(n)

#include <bits/stdc++.h>
using namespace std;
const int maxn=500020;
const int maxm=1200000;
int to[maxm],nxt[maxm],head[maxn],num;
void add(int x,int y){num++;to[num]=y;nxt[num]=head[x];head[x]=num;}
int n,K;
int dep[maxn],fa[maxn];
void dfs_pre(int p,int F)
{
    dep[p]=dep[F]+1;fa[p]=F;
    for(int i=head[p];i;i=nxt[i])
    {
        if(to[i]==fa[p]) continue;
        dfs_pre(to[i],p);
    }
}
int dis[maxn],vis[maxn];
queue<int> Q;
int O[maxn];
void spfa()
{
    while(!Q.empty())
    {
        int p=Q.front();Q.pop();
        for(int i=head[p];i;i=nxt[i])
        {
            if(dis[to[i]]>dis[p]+1) 
            {
                dis[to[i]]=dis[p]+1;
                if(!vis[to[i]]) vis[to[i]]=1,Q.push(to[i]);
            }
        }
    }
}
int d[maxn];
void dfs(int p,int s)
{
    d[p]=1;
    for(int i=head[p];i;i=nxt[i])
    {
        int v=to[i];
        if(dis[v]!=s-1||d[v]) continue;
        dfs(v,s-1);
    }
}
bool cmp(int x,int y){return dep[x]>dep[y];}
int ans;
vector<int> Ans;
int main()
{
//  freopen("p.in","r",stdin);
//  freopen("p.out","w",stdout);
    scanf("%d%d",&n,&K);
    for(int i=1;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs_pre(1,0);
    memset(dis,0x7f,sizeof(dis));
    for(int i=1;i<=K;i++)
    {
        scanf("%d",&O[i]);
        dis[O[i]]=0; vis[O[i]]=1;
        Q.push(O[i]);
    }
    spfa();
    sort(O+1,O+1+K,cmp);
    for(int i=1;i<=K;i++)
    {
        if(d[O[i]]) continue;
        int f=O[i],v=0;
        while(fa[f]&&dis[fa[f]]==dis[f]+1) f=fa[f];
        dfs(f,dep[O[i]]-dep[f]);
        ans++;
        Ans.push_back(f);
    }
    printf("%d\n",ans);
    for(auto x:Ans)
    {
        printf("%d ",x);
    }
    return (0-0);
}