求助 神秘RE
查看原帖
求助 神秘RE
256970
xie_lzh楼主2022/5/21 08:50

不知道怎么的,dfs跑到3万多本地就RE了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
	int r=0,f=1;
	char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')f=0;
		c=getchar();
	}
	while(isdigit(c))
	{
		r=(r<<1)+(r<<3)+c-48;
		c=getchar();
	}
	return f?r:-r;
}
const int N=1e6;
int n,m,k,s,need[N],cnt3[N<<1];
int to[N<<1],nxt[N<<1],val[N],head[N],cnt=1,id[N<<1];
void add(int u,int v,int pos)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
	id[cnt]=pos;
}

int dfn[N],fa[N][15],dep[N],idx;
void dfs(int now,int f)
{
//	printf("%lld\n",now);
//	printf("wocao%lld\n",now);
	dep[now]=dep[f]+1;
	dfn[now]=++idx;
	fa[now][0]=f;
//	printf("%lld\n",now);
	for(int i=1;i<=14;i++)
		fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=head[now];i;i=nxt[i])
	{
//		if(now==32374)
//			puts("qwq");
		int v=to[i];
//		if(now==32374)
//			printf("%lld\n",v);
		if(v==f) continue;
		dfs(v,now);
	}
}

int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=14;i>=0;i--)
		if(dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
	if(x==y) return x;
	for(int i=14;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int stk[N],top;
bool cmp(int x,int y)
{
	return dfn[x]<dfn[y];	
}

void work()
{
	sort(need+1,need+1+s,cmp);
	for(int i=1;i<s;i++) 
	{
		val[need[i]]++;
		val[need[i+1]]++;
		val[LCA(need[i],need[i+1])]-=2;
	}
	val[need[1]]++;
	val[need[s]]++;
	val[LCA(need[1],need[s])]-=2;
}

int ans[N],sum; 
void dfs2(int now,int f)
{
	for(int i=head[now];i;i=nxt[i])
	{
		int v=to[i];
		if(v==f) continue;
		dfs2(v,now);
		val[now]+=val[v];
		if(val[v]>=2*k) 
			ans[++sum]=id[i];
	}
}
signed main()
{
	freopen("P6572_1.in","r",stdin);
	
	n=read(); m=read(); k=read();
	for(int i=1;i<n;i++)	
	{
		int u=read(),v=read();
		add(u,v,i); add(v,u,i);
	} 
	dfs(1,0);
	for(int i=1;i<=m;i++)
	{
		s=read();
		for(int j=1;j<=s;j++)
			need[j]=read();
		work();
	}
	dfs2(1,0);
	printf("%lld\n",sum);
	sort(ans+1,ans+1+sum);
	for(int i=1;i<=sum;i++)
		printf("%lld ",ans[i]);
} 
2022/5/21 08:50
加载中...