题面传送门：P8428 [COI 2020] Pastiri。
首先树上覆盖有个经典贪心，每次找到最深的点并找到可覆盖它最浅的祖先覆盖，感性理解一下，由于这是最深的点，没有更深的点，因此兄弟子树显然不优，而找最浅祖先可以覆盖更多的点。
那么我们对每个羊按照深度大到小排序，然后找到能覆盖这个羊的最浅祖先，然后将这个点能覆盖的其它羊标记了，下次无需考虑。
如果这样暴力做是 \(O(n^2)\) 的，考虑优化。
考虑计算每个点到最近的羊的距离记为 \(d\)，然后爬祖先时直接判断 \(d_{fa_u}= d_u +1\) 即可，至于覆盖其他羊，直接 dfs 即可，显然走过的点不会重复走，因此均摊是对的。
至于如何求每个点到最近的羊的距离，多源最短路即可，使用 bfs 实现。
#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N=5e5+10;
inline int read(){char c=getchar();int f=1,ans=0;while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();return ans*f;
}
vector<int>g[N];
int n,k,a[N];
int dep[N],fa[N];
void dfs(int u,int fa){::fa[u]=fa,dep[u]=dep[fa]+1;for (auto v:g[u]) if (v^fa) dfs(v,u);
}
int d[N],vis[N];
inline void bfs(){memset(d,0x3f,sizeof(d));queue<int>q;for (int i=1;i<=n;i++) q.push(a[i]),d[a[i]]=0;while(!q.empty()){int u=q.front();q.pop();if (vis[u]) continue;vis[u]=1;for (auto v:g[u]) if (d[v]>d[u]+1) d[v]=d[u]+1,q.push(v);}
}
inline bool cmp(int x,int y){return dep[x]>dep[y];}
void dfs1(int u,int x){vis[u]=1; for (auto v:g[u]) if (!vis[v]&&d[v]==x-1) dfs1(v,x-1);
}
main(){n=read(),k=read();for (int i=1,u,v;i<n;i++) u=read(),v=read(),g[u].push_back(v),g[v].push_back(u);for (int i=1;i<=k;i++) a[i]=read();dfs(1,0);sort(a+1,a+k+1,cmp);bfs();memset(vis,0,sizeof(vis));vector<int>anss;for (int i=1;i<=k;i++) if (!vis[a[i]]){int x=a[i],y=a[i];while(fa[y]&&d[fa[y]]==d[y]+1) y=fa[y];dfs1(y,dep[x]-dep[y]);anss.push_back(y); }printf("%lld\n",(int)anss.size());for (auto i:anss) printf("%lld ",i);return 0;
}