被联考创出 shit 了。
考虑一种极限情况：每个点指向父亲。那么这种情况我们会顺着欧拉序完整地把整棵树都走一遍。
但是初始的时候不一定每个点都指向父亲。发现我们走过 \(O(n^2)\) 步就能到达上面的极限情况。比较显然，因为每次扩展至少使一个点从不指向父亲变成指向父亲（称一次扩展为，不处于极限情况时，根结点走完一遍又回到自己的过程）。
考虑若一个点初始不指向父亲，那么第一次扩展到它时，它还没来得及扩展所有子结点就回到父亲了。但是第二次扩展可以扩展所有子结点。所以一个点至多需要访问 \(2\) 次。基于此考虑用一个队列维护还需要被访问的点，若遇到一个点没扩展完所有子结点就返回，就把它 push 进队列。
考虑如何回答询问。注意到每次扩展经过的结点编号序列，一定是最终欧拉序的子序列。于是我们把询问离线下来，扩展时把对应点的对应位置插入序列，查询就查一个下标第 \(k\) 大。可以使用树状数组维护。对于走到第 \(k\) 步时已经把整棵树扩展完的询问，因为它的周期是整棵树的欧拉序，所以也可以快速回答。
时间复杂度 \(O((n + q) \log n + q \log q)\)。
code
// Problem: P7830 [CCO2021] Through Another Maze Darkly
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7830
// Memory Limit: 1 MB
// Time Limit: 8000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 22, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 22], *p1 = buf, *p2 = buf;
inline ll read() {
char c = getchar();
ll x = 0;
for (; !isdigit(c); c = getchar()) ;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x;
}
const int maxn = 1600100;
ll n, m, tt, fa[maxn], fd[maxn], ans[maxn], pt[maxn], a[maxn], tot, b[maxn], cnt;
bool vis[maxn];
pii qq[maxn];
vector<pii> G[maxn];
vector<int> vc[maxn];
void dfs(int u, int f) {
for (pii &p : G[u]) {
int v = p.fst;
if (v == f) {
p.scd = fd[u];
continue;
}
p.scd = ++tt;
fa[v] = u;
fd[v] = tt;
dfs(v, u);
}
}
void dfs2(int u, int fa) {
int t = pt[u], len = (int)G[u].size();
while (1) {
pt[u] = (pt[u] + 1) % len;
if (pt[u] == t && u > 1) {
break;
}
int v = G[u][pt[u]].fst;
a[++tot] = v;
b[tot] = G[u][pt[u]].scd;
dfs2(v, u);
a[++tot] = u;
b[tot] = G[u][pt[u]].scd;
if (pt[u] == t && u == 1) {
break;
}
}
}
namespace BIT {
int c[maxn];
inline void update(int x, int d) {
++cnt;
for (int i = x; i <= n * 2 - 2; i += (i & (-i))) {
c[i] += d;
}
}
inline int kth(int k) {
int p = 0;
for (int i = __lg(n * 2 - 2); ~i; --i) {
if (p + (1 << i) <= n * 2 - 2 && c[p + (1 << i)] < k) {
p += (1 << i);
k -= c[p];
}
}
return p + 1;
}
}
vector<int> nxt;
void dfs3(int u) {
int len = (int)G[u].size();
while (1) {
pt[u] = (pt[u] + 1) % len;
int v = G[u][pt[u]].fst, id = G[u][pt[u]].scd;
if (vis[id]) {
break;
}
if (v == fa[u]) {
nxt.pb(u);
break;
}
BIT::update(vc[id][0], 1);
dfs3(v);
vis[id] = 1;
BIT::update(vc[id][1], 1);
}
}
void solve() {
n = read();
m = read();
for (int i = 1, k; i <= n; ++i) {
k = read();
while (k--) {
G[i].pb(read(), 0);
}
}
dfs(1, -1);
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < (int)G[i].size(); ++j) {
if (G[i][j].fst == fa[i]) {
pt[i] = j;
break;
}
}
}
dfs2(1, -1);
for (int i = 1; i <= tot; ++i) {
vc[b[i]].pb(i);
}
for (int i = 1; i <= m; ++i) {
qq[i] = mkp(read(), i);
}
sort(qq + 1, qq + m + 1);
mems(pt, 0);
ll s = 0, j = 1;
queue<int> q;
q.push(1);
while (cnt < tot) {
ll lst = s;
vector<int>().swap(nxt);
while (q.size()) {
int u = q.front();
q.pop();
dfs3(u);
}
for (int x : nxt) {
q.push(x);
}
s += cnt;
while (j <= m && qq[j].fst <= s) {
ans[qq[j].scd] = a[BIT::kth(qq[j].fst - lst)];
++j;
}
}
while (j <= m) {
ans[qq[j].scd] = a[(qq[j].fst - s - 1) % tot + 1];
++j;
}
for (int i = 1; i <= m; ++i) {
printf("%lld\n", ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}