UPD:更新了部分代码

Through Another Maze Darkly

很有意思的一道思维题。

无论是思路上还是实现上。

此篇题解重点在如何实现题目相关查询上。

首先发现只要时间够长，每一个点都会被经过。

手摸样例观察性质，猜测其最终一定会进入一个周期。

一个感性的证明：

对于一个点，其只能从其父亲到达，且若干时刻后一定会再次回到其父亲。考虑v回到父亲时的灯的方向，显然是指向其父亲。

在灯指向父亲后，再次由父亲遍历到此节点时，其一定能遍历到其所有的儿子。遍历完其为根的子树后，灯指向父亲，走到父亲节点，退出这棵子树。此时该节点灯仍指向父亲。

对于灯指向父亲的点，其遍历相邻点的遍历顺序唯一。

发现当所有节点的灯都指向父亲后（发现此状态一定能够到达），遍历序列必定进入周期，即在一定要求下的原图的欧拉序。

对于周期内的点较为好求，如何处理周期前的点？

我们定义灯指向父亲的点是好点，没有指向父亲的点是坏点。

定义从 $1$ 结点出发后又回到 $1$ 节点为一次遍历，一次遍历的遍历顺序为此次遍历经过的点编号依次排列生成的序列（此点编号在被遍历到和由儿子回溯都加入一次）（即为欧拉序）。

考虑每一个点遍历时能访问到的儿子节点。

定义顺时针访问顺序为此点在另一点顺时针方向上，从激光灯指向的下一个节点开始编号的号码大小。

若此点为好点，则所有儿子一定能被访问。

若此点为坏点，则会从灯初始指向节点的下一个节点开始访问，直到访问到父亲节点，此时会退出这棵子树，剩下的顺时针访问顺序在父亲后的儿子节点则不会被访问。（注意到在退出时灯指向父亲，下一次访问此点则会从顺时针访问顺序比父亲恰好大一的点开始访问，一直访问到访问顺序比父亲恰好小一的点，即所有儿子又一定能被访问）

当一个点所有儿子都能被访问时，此点一定是好点。

观察坏点遍历过程发现，一个坏点在经过一次遍历后能变成好点。

观察好点遍历过程发现，一个好点永远不会变坏。

由于一棵子树的欧拉序连续，所以可以发现，每一次遍历的遍历顺序都是原图的欧拉序上的一个子序列。

在最后时刻，进入周期后，只有好点时，遍历序列就是原图的欧拉序。

由此我们转入维护欧拉序的子序列。

每次要找到欧拉序上的第一个坏点。

如何快速的向后跳，找第一个坏点？别急。你先别急。

这里的实现挺神奇的。

思考坏点的遍历过程（可以再看看上文），对于顺时针遍历顺序比其父亲小的坏点的儿子，在遍历坏点时会获得较高的遍历优先级，而顺时针遍历顺序比父亲大的儿子则在遍历坏点时不会被遍历。

如何将这样的过程转到欧拉序上？

可以发现，若所有的点都为好点，每一个点遍历自己儿子的顺序是：

顺时针遍历顺序比父亲大的儿子（从小往大）$\rightarrow$ 顺时针遍历顺序比父亲小的儿子（从小往大）$\rightarrow$ 回到父亲（回溯）

而对于坏点，其遍历顺序为：

顺时针遍历顺序比父亲小的儿子（从小往大）$\rightarrow$ 回到父亲（回溯）（此时其变为好点）

坏点相当于跳过了在最终状态下优先级最高的顺时针遍历顺序比父亲大的儿子。

也即在欧拉序上跳过了遍历这些儿子所生成的遍历序列。

而在每次坏点被遍历，成为好点后，这些儿子生成的遍历序列相当于插入了此前的遍历序列。

插入操作太难维护，注意到最终状态是确定的，也即是原图的欧拉序。

可以用类似标记的方法，跳过所有没有打标记的点，直接找到第一个有标记的点，取消其标记。

每次的遍历顺序就是所有没有打标记的点。

因为每次标记只会消除不会再打上，可以考虑用并查集来加速这个跳标记的过程。

在欧拉序上，初始状态时，每一个初始状态下的好点并查集里的父亲都是欧拉序上的下一个位置，每一个初始状态下的坏点并查集里的父亲是自己所在的位置。

我们把并查集建在了欧拉序上。

这样每次执行并查集里的 getfa 操作就可以快速的找到下一个坏点。

相当于在原图中遍历到了下一个可以被遍历的坏点。

其中，好点 对应上文 没有标记的点，坏点 对应上文 有标记的点。

好点指向下一个位置 对应 没有标记的点不会停留，同时对应好点会直接按顺序遍历自己所有的儿子，坏点指向自己 对应 在自己位置停留，同时对应我们需要在此时分析坏点应遍历哪些儿子。

那么坏点变好即为更改其父亲为下一个位置。

对于好点，在并查集上就直接跳过去了，基本没有什么实现上的细节。

考虑坏点。

Q : 我们怎么从坏点出发找到下一个遍历的点？

观察坏点的遍历顺序。其顺时针遍历顺序比起父亲大的儿子都会被跳过，但其在后续遍历过程中则排在所有儿子的前面。这启发我们对每一个坏点构造一个指针，使其指向自己为坏点时遍历的第一个儿子（即顺时针遍历顺序最小的儿子）在欧拉序中出现的第一个位置（相当于遍历这个儿子）。

可以发现顺时针遍历顺序比其父亲还要大的坏点的儿子，欧拉序上在顺时针遍历顺序小的儿子的前面。

在跳到坏点时只需要跳到其这个顺时针遍历顺序最小儿子就能避免遍历到其遍历顺序大的儿子。

救命呀我要不认识遍历这个词了

Q : 我们需要让坏点在欧拉序中的所有位置都指向自身位置吗？（注意到一个点（除根）会在欧拉序上出现其度数次）

这样既繁琐又麻烦。

观察坏点的遍历过程，我们只需要在第一次遍历到坏点时知道此处为坏点就行，在后续由儿子回溯时不需考虑其好或坏。

对应于欧拉序上我们只让坏点第一次出现的位置并查集上的父亲指向自己。

Q : 那么在跳到坏点时应该做什么操作？

观察坏点的遍历过程，我们需要做的只有将其变成好点（并查集上指向下一个位置），然后跳到前文说的坏点遍历的第一个儿子即可。

Q : 怎么处理未进入循环区间时的询问？

可以发现，每次向后跳跃都是跳过了一段连续的区间（因并查集要不指向自身要不指向下一个位置），因此可以将询问离线，排序后用一个指针判断这个询问的时间是否已经达到，若达到则可以通过下标计算此询问所到达的点。

对于进入循环区间的点，减去前部分未进入造成的时间损耗，再模一个欧拉序长度知道其在欧拉序上的哪一个位置了。

代码

const int N=8e5+5;

vector<int> e[N];//顺时针遍历顺序 

int dfn[2*N],tot;//欧拉序，两倍长度 

int fa[2*N];//并查集 

void init(int n){for(int i=1;i<=2*n;i++)fa[i]=i+1;}//初始化 
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}//路径压缩 

int fnum[N];//父亲编号在vector里的位置 

void dfs(int u,int faa)
{
	dfn[++tot]=u;
	if(u==1)//对根特殊处理，没有父亲 
		fnum[u]=-1;
	else
		for(int i=0;i<e[u].size();i++)
			if(e[u][i]==faa)//找到父亲的顺时针遍历顺序 
			{
				fnum[u]=i;
				break;
			}
	for(int i=fnum[u]+1;i<e[u].size();i++){//遍历顺序更大的点
		int v=e[u][i];
		dfs(v,u);
		dfn[++tot]=u;
	}
	for(int i=0;i<fnum[u];i++){//遍历顺序更小的点 
		int v=e[u][i];
		dfs(v,u);
		dfn[++tot]=u;
	}
}

struct qst{
	int w,id;
}q[N];//存储询问 

int ans[N];//答案 

bool cmp(qst aaa,qst bbb){return aaa.w<bbb.w;}

vector<int> stk[N];//寻找每一个坏点到达的第一个儿子 

int nxt[2*N];//坏点的指针 
bool tag[N];//在欧拉序中是否是第一次出现 

signed main()
{
	int n=read(),Q=read();
	for(int i=1;i<=n;i++)
	{
		int len=read()-1,fst=read();//第一个位置优先级最低，因为先转灯再走 
		while(len--)
			e[i].push_back(read());
		e[i].push_back(fst);//按照顺时针遍历顺序压入 
	}
	dfs(1,0);//求出原图的欧拉序（即每一个点都不考虑灯的方向，顺时针走的欧拉序） 
	init(n);//并查集初始化 
	for(int i=1;i<=Q;i++)
		q[i]={read(),i};//笔者这里开了define int long long 
	sort(q+1,q+1+Q,cmp);
	int num=-1;//坏点个数，dfn[1]也会被标记为坏点，提前减去 
	for(int i=1;i<=tot;i++){
		if(tag[dfn[i]]==0&&fnum[dfn[i]]!=e[dfn[i]].size()-1)//第一次出现且灯没有指向父亲 
			fa[i]=i,num++;//标记为坏点 
		tag[dfn[i]]=1;//出现过 
	}
	for(int i=tot;i>=1;i--)
		stk[dfn[i]].push_back(i);//把每一个点每次在欧拉序上的位置倒序压入 
	for(int i=1;i<=tot;i++)
		if(fa[i]==i)
			nxt[i]=stk[dfn[i]][fnum[dfn[i]]];//坏点下一个要访问的点，顺时针遍历顺序恰好比父亲大1的儿子
	fa[1]=2;fa[tot]=tot;
   nxt[tot]=tot;//可能跳到的唯一好点，特殊处理一下 
	
	//预处理结束
	
	//处理在周期外的遍历顺序 
	int d=0,p=1;//时间偏移量和询问指针 
	while(num>0)//还有坏点 
	{
		int nw=1;//当前节点 
		while(nw<tot)//因为欧拉序首尾相连，最后一个位置没有贡献 
		{
			int fff=getfa(nw);//下一个坏点 
			int len=fff-nw;//跳跃的区间长度 
			while(len+d>=q[p].w&&p<=Q)//处理满足条件的询问 
				ans[q[p].id]=dfn[nw+q[p].w-d],p++;
			if(fff!=tot)
				fa[fff]=fff+1,num--;//变成好点 
			d+=len;//时间增加 
			nw=nxt[fff];//跳到坏点第一个被遍历的儿子 
		}
	}
	while(p<=Q)//处理在周期里的遍历顺序 
		ans[q[p].id]=dfn[(q[p].w-d-1)%(tot-1)+2],p++;//笔者加载的欧拉序长度为2n-1,但实际上用到的只有2n-2个数，因欧拉序首尾相连
	for(int i=1;i<=Q;i++)
		print(ans[i]),pc('\n');
	return 0;
}