自动搬运

查看原文

来自洛谷，原作者为

	slzs 喜欢什么的，不说才感动人呢

搬运于2025-08-24 22:22:03，当前版本为作者最后更新于2020-10-30 10:32:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

对于每一个副部长，我们把被他选择的点按dfs序从小到大排序，依次使相临两点最短路径上的边的权值+1。最后判断有哪些边的权值不小与2*k即可。

举个例子

如图：若副部长选择的点为4,5,7。(可以发现本来只算一次的边，恰好算了2次)

从4到5，从5到7，从7到4。

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <iomanip>
using namespace std;
const int N=401000;
int n,m,k,num,tot=0,dotot=0,tp=0;
int lst[N],dfn[N],sum[N],laz[N],ls[N],rs[N],q[N],u[N],v[N];
int id[N],dep[N],top[N],son[N],siz[N],fa[N];
struct A
{
	int fir,nex,go,type;
}a[N];
inline bool cmp(int E,int F)
{
	return dfn[E]<dfn[F];
}
void add(int x,int y)
{
	a[++tot].nex=a[x].fir;
	a[x].fir=tot;
	a[tot].go=y;
}
inline int read()
{
	int x=0,minus=0;char ch;
	while (!isdigit(ch=getchar())) minus|=(ch=='-');
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return minus?-x:x;
}
void dfs1(int x,int f)
{
	dfn[x]=++dotot;//dfs序
	fa[x]=f;
	dep[x]=dep[f]+1;
	siz[x]=1;
	for (register int i=a[x].fir;i;i=a[i].nex)
	{
		int y=a[i].go;
		if (y==f) continue;
		dfs1(y,x);
		siz[x]+=siz[y];
		if (siz[son[x]]<siz[y]) son[x]=y;
	}
}
void dfs2(int x,int topf)
{
	id[x]=++dotot;//线段树用的
	top[x]=topf;
	if (!son[x]) return ;
	dfs2(son[x],topf);
	for (register int i=a[x].fir;i;i=a[i].nex)
	{
		int y=a[i].go;
		if (y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}
void build(int k,int l,int r)
{
	ls[k]=l,rs[k]=r;
	if (l==r) return ;
	int mid=(l+r)>>1;
	build(k<<1,l,mid),build(k<<1|1,mid+1,r);
}
void down(int k)
{
	if (laz[k]==0) return ;
	laz[k<<1]+=laz[k];
	laz[k<<1|1]+=laz[k];
	sum[k<<1]+=(rs[k<<1]-ls[k<<1]+1)*laz[k];
	sum[k<<1|1]+=(rs[k<<1|1]-ls[k<<1|1]+1)*laz[k];
	laz[k]=0;
}
void change(int k,int x,int y)
{
	if (ls[k]>=x&&rs[k]<=y)
	{
		sum[k]+=rs[k]-ls[k]+1;
		laz[k]++;
		return ;
	}
	down(k);
	if (x<=rs[k<<1]) change(k<<1,x,y);
	if (y>=ls[k<<1|1]) change(k<<1|1,x,y);
	sum[k]=sum[k<<1]+sum[k<<1|1];
}
inline int cheak(int k,int x)
{
	if (ls[k]==rs[k]) return sum[k];
	down(k);
	if (x<=rs[k<<1]) return cheak(k<<1,x);
	else return cheak(k<<1|1,x);
}
void chain(int x,int y)
{
	while (top[x]!=top[y])
	{
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		change(1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if (x==y) return ;
	if (dep[x]>dep[y]) swap(x,y);
	change(1,id[son[x]],id[y]);
}
signed main()
{
	n=read(),m=read(),k=read();
	for (register int i=1,x,y;i<n;++i)
	x=read(),y=read(),add(x,y),add(y,x),u[i]=x,v[i]=y;
	tot=0,dfs1(1,0),dotot=0,dfs2(1,1),build(1,1,n);//预处理
	while (m--)
	{
		num=read();
		for (register int i=1;i<=num;++i) lst[i]=read();
		sort(lst+1,lst+1+num,cmp);//按dfs序排序
		for (register int i=1;i<num;++i) chain(lst[i],lst[i+1]);
		chain(lst[1],lst[num]);//依次使相临两点最短路径上的边的权值+1
	}
	for (register int i=1;i<n;++i)
	{
		if (dep[u[i]]<dep[v[i]]) swap(u[i],v[i]);//树剖把边权存到儿子那了
		if (cheak(1,id[u[i]])>=2*k) q[++tp]=i;
	}
	printf("%d\n",tp);
	for (register int i=1;i<=tp;++i) printf("%d ",q[i]);//输出答案
	return 0;
}