最坏走 \(n^2\) 次后，所有点的激光指向器都指向其父亲，此时走的就是欧拉序了，所以问题集中在优化前面的 \(n^2\) 次。
称激光指向器指向其父亲的结点为好点，激光指向器不指向其父亲的结点为坏点。
考虑好坏点间的转化，模拟后不难发现好点始终是好点，坏点经过一次遍历后变为好点。
而又因为坏点在第一次被遍历时其子树不会被完全遍历，因此每个坏点都需要遍历两遍。
考虑每次遍历形成的序列有什么性质。
对每个点，从激光指示器所指结点顺时针方向的下一个结点（即每个点最开始会走到的点）按顺时针方向给每个点的子结点排序，称这个顺序为 遍历顺序。
那么对于一个好点，其所有子结点都能够被遍历到，顺序是：
遍历顺序大于父结点的结点（从小到大）——遍历顺序小于父结点的结点（从小到大）——父结点
对于一个坏点，只有部分子结点能够被遍历到，顺序是：
遍历顺序小于父结点的结点（小到大）——父结点
二者间相差的是是否遍历遍历顺序大于父结点的结点，因此，在有坏点存在时，每次遍历形成的序列都是欧拉序的子序列。
问题来到如何找坏点，我们可以用并查集来维护坏点的信息。
具体来说，好点的父亲是它在欧拉序上的下一个点，坏点的父亲就是它自己，这样每次找父亲就能直接找到下一个坏点。
剩下的就是计算 & 统计答案了，离线求解，询问需要排序。
时间复杂度 \(\mathcal O[n \alpha (n) + q \log q]\)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 8e5 + 10;
int n, Q, tot, fid[N], ans[N], dfn[N << 1], nxt[N << 1];
bool vis[N];
struct Query {
int id; ll k;
bool operator<(const Query &rhs) const {return k < rhs.k;}
} q[N];
vector<int> G[N], rec[N];
namespace DSU {
int fa[N << 1];
void init(int n) {for (int i = 1; i <= n; i++) fa[i] = i + 1;}
int find(int x) {return x == fa[x] ? x : (fa[x] = find(fa[x]));}
}
void dfs(int u, int fa) {
dfn[++tot] = u;
if (u == 1) fid[u] = -1;
else for (int i = 0; i < G[u].size(); i++) if (G[u][i] == fa) {fid[u] = i; break;}
for (int i = fid[u] + 1; i < G[u].size(); i++) dfs(G[u][i], u), dfn[++tot] = u;
for (int i = 0; i < fid[u]; i++) dfs(G[u][i], u), dfn[++tot] = u;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> Q;
for (int i = 1; i <= n; i++) {
int k; cin >> k; G[i].resize(k);
for (int &v : G[i]) cin >> v;
G[i].emplace_back(*G[i].begin()), G[i].erase(G[i].begin());
}
for (int i = 1; i <= Q; i++) q[i].id = i, cin >> q[i].k;
dfs(1, 0), DSU::init(n << 1); int bad = -1;
for (int i = 1; i <= tot; i++) {
if (!vis[dfn[i]] && fid[dfn[i]] != G[dfn[i]].size() - 1) bad++, DSU::fa[i] = i;
vis[dfn[i]] = 1;
}
for (int i = tot; i; i--) rec[dfn[i]].emplace_back(i);
for (int i = 1; i <= tot; i++) if (DSU::fa[i] == i) nxt[i] = rec[dfn[i]][fid[dfn[i]]];
DSU::fa[1] = 2, DSU::fa[tot] = nxt[tot] = tot;
sort(q + 1, q + Q + 1); ll p = 0; int cur = 1;
while (bad) {
int now = 1;
while (now < tot) {
int fnow = DSU::find(now), len = fnow - now;
while (cur <= Q && q[cur].k <= p + len) ans[q[cur].id] = dfn[now - p + q[cur].k], cur++;
if (fnow != tot) DSU::fa[fnow] = fnow + 1, bad--;
p += len, now = nxt[fnow];
}
}
while (cur <= Q) ans[q[cur].id] = dfn[(q[cur].k - p - 1) % (tot - 1) + 2], cur++;
for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
return 0;
}