自动搬运

查看原文

来自洛谷，原作者为

	cc0000 曾瞥见零光片羽，遂毕生追逐代替

搬运于2025-08-24 22:38:57，当前版本为作者最后更新于2022-09-11 22:14:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

树上贪心神题

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

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

这样做复杂度是对的是因为在标记时可以用 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);
}