RT

LCT就算常数再大也不应该在几万的点TLE吧？

有大佬有兴趣帮菜鸡卡下常或者优化一下吗？

蒟蒻的代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")

#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>

using namespace std;

#define il inline
#define re register
#define file(s) freopen(#s".in","r",stdin),freopen(#s".out","w",stdout)
#define mp(x,y) make_pair(x,y)

typedef pair<int,int> Pair;

const int N=1e6+10;

namespace FastIO
{
	char buf[1<<21],buf2[1<<21],*p1=buf,*p2=buf;
	int p4,p3=-1;
	il int getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
	il void Flush(){fwrite(buf2,1,p3+1,stdout),p3=-1;}
	#define isdigit(ch) (ch>=48&&ch<=57)
	template <typename T>
	il void read(T &x)
	{
		re int f=0;x=0;re char ch=getc();
		while(!isdigit(ch)) f|=(ch=='-'),ch=getc();
		while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getc();
		x=f?-x:x;
	}
	template <typename T>
	il void print(T x)
	{
		if(p3>(1<<20)) Flush();
		if(x<0) buf2[++p3]=45,x=-x;
		re int a[50]={};
		do{a[++p4]=x%10+48;}while(x/=10);
		do{buf2[++p3]=a[p4];}while(--p4);
	}
}
using namespace FastIO;

int cnt;
struct edge{int u,v,w;}e[N];
 
struct Link_Cut_Tree
{
	int fa[N],son[2][N],Max[N],tag[N];
	il void init()
	{
		memset(fa,0,sizeof(fa));
		memset(son,0,sizeof(son));
		memset(Max,0,sizeof(Max));
		memset(tag,0,sizeof(tag));
		return;
	}
	#define ls(p) (son[0][p])
	#define rs(p) (son[1][p])
	#define indent(x,f) (rs(f)==x)
	#define notrt(x) (ls(fa[x])==x||rs(fa[x])==x)
	#define connect(x,f,s) (fa[x]=f,son[s][f]=x)
	il void pushup(int x)
	{
		Max[x]=x;
		if(e[Max[ls(x)]].w>e[Max[x]].w) Max[x]=Max[ls(x)];
		if(e[Max[rs(x)]].w>e[Max[x]].w) Max[x]=Max[rs(x)];
		return;
	}
	#define reverse(x) (swap(ls(x),rs(x)),tag[x]^=1)
	il void pushdown(int x)
	{
		if(!tag[x]) return;
		if(ls(x)) reverse(ls(x));
		if(rs(x)) reverse(rs(x));
		tag[x]=0;return;
	}
	int st[N],top;
	il void pushall(int x)
	{
		top=0;
		while(notrt(x)) st[++top]=x,x=fa[x];
		pushdown(x);
		while(top) pushdown(st[top--]);
		return;
	}
	il void rotate(int x)
	{
		re int f=fa[x],ff=fa[f],k=indent(x,f);
		connect(son[k^1][x],f,k);
		fa[x]=ff;
		if(notrt(f)) son[indent(f,ff)][ff]=x;
		connect(f,x,k^1);
		pushup(f);pushup(x);
		return;
	}
	il void splay(int x)
	{
		pushall(x);
		while(notrt(x))
		{
			re int f=fa[x],ff=fa[f];
			if(notrt(f)) rotate(indent(x,f)^indent(f,ff)?x:f);
			rotate(x);
		}
		return;
	}
	il void access(int x)
	{
		re int flag=x==5;
		for(re int y=0;x;x=fa[y=x])
			splay(x),rs(x)=y,pushup(x);
		return;
	}
	il void makert(int x){access(x),splay(x),reverse(x);return;}
	il int getrt(int x)
	{
		access(x);splay(x);
		while(ls(x)) pushdown(x),x=ls(x);
		splay(x);return x;
	}
	il void link(int u,int v)
	{
		makert(u);
		if(getrt(v)==u) return;
		fa[u]=v;return;
	}
	il void cut(int u,int v)
	{
		makert(u);
		if(getrt(v)^u||fa[v]^u||ls(v)) return;
		fa[v]=rs(u)=0;pushup(u);
		return;
	}
	il void split(int u,int v){makert(u);access(v);splay(v);return;}
	il int query(int u,int v){split(u,v);return Max[v];}
}T;
 
int n,m,q;
int k,flag;
Pair tmp[N];
int top;

int main()
{
	read(n),read(m);cnt=n;T.init();
	for(re int i=1,u,v,w,y;i<=m;++i)
	{
		read(u),read(v),read(w),e[++cnt]=(edge){u,v,w};
		if(T.getrt(v)==T.getrt(u))
		{
			y=T.query(u,v);
			if(e[y].w<=w) continue;
			T.cut(e[y].u,y);T.cut(e[y].v,y);
		}
		T.link(u,cnt);T.link(v,cnt);
	}
	read(q);
	while(q--)
	{
		read(k);flag=1;
		for(re int i=1,x,y;i<=k;++i)
		{
			read(x);x+=n;
			if(flag)
			{
				y=T.query(e[x].u,e[x].v);
				if(e[y].w<e[x].w){flag=0;continue;}
				tmp[++top]=mp(x,e[x].w);T.splay(x);e[x].w=0;
				if(y^x)
				{
					T.cut(e[y].u,y);T.cut(e[y].v,y);
					T.link(e[x].u,x);T.link(e[x].v,x);
				}
			}
		}
		while(top)
		{
			T.splay(tmp[top].first);
			e[tmp[top].first].w=tmp[top].second;
			--top;
		}
		puts(flag?"YES":"NO");
	}
	Flush();return 0;
}