CCO2021 Through Another Maze Darkly

· · 题解

不需要任何 log 数据结构的做法。

首先考虑一个暴力结论：我们走有限次之后（实际上是 O(n^2)，极限情况是都指向子节点的链），一定会达成以下的局面：所有节点（除了跟节点）都指向父亲。然后就会根据欧拉游走序进行循环了。所以现在的重点是要处理出在循环之前的情况。

注意，在这个欧拉游走序中，我们每个节点的儿子顺序，应该是在原出边顺序中，从父节点之后的那个儿子开始，父节点之前的那个儿子结束，形成的一个顺序。

我们把其最终结果的欧拉游走序给求出来。如果我们在某一时刻”解决“了一个树上节点，那么在之后的时刻，遇到这个点就直接按照欧拉游走序上的往后走就行了。所以对于欧拉序上的每一个位置，我们可以打一个标记。而当我们对于 u，它走出了自己的子树，那么此时它一定会指向自己的父节点，于是自己就被解决了，把自己在欧拉序上出现的位置的标记全部删掉。

我们假设我们现在在欧拉序的没有标记的 x 上，那么我们会一路走到第一个有标记的位置 y。此时 y 一定还没有被经过（因为如果一个点有标记那么子树内的点也必然有标记，所以 x 在 y 子树外，所以如果以前经过过 y 那么就一定走出过 y 的子树，与其未被解决矛盾）。所以此时我们就可以跳到 y 的在原树上的第二个出边处，然后继续往下走（因为会直接转到第二个孩子）。其实在此时，我们就已经可以把 y 的节点解决了。因为从此之后，它的遍历顺序就和我们最终的欧拉游走序相同了。

所以我们的操作就是：对于 x，我们先删除 x 的所有标记，跳到 x 在原树上的第二个出边处（即欧拉序上那个点在 x 之后的最近出现的位置）。然后当 x 上没有标记（即其原来的第二个儿子为自己的父节点，或者自己是叶节点），就顺序走到下一个标记处。维护每个节点之后的第一个标记，这可以直接上一个并查集。而我们同时也维护时间。走到下一个节点的时间区间 [l,r] 可能会囊括一些问询，而这段时间内走的是一段连续的欧拉序，我们把这些问询给处理掉即可。

复杂度正确，因为我们每次遍历到标记节点就会删除一些标记，而两次标记访问之间最多有一次非标记访问。

要对问询排序所以得勉为其难地带个 log。

复杂度 O(n\alpha(n)+q\log q)。

Update："你可以基排的"，所以可以直接做到 O(n\alpha(n)+q)。

const int N=1.6e6+9;

int n,Q,nxt[N],fa[N],dfn[N],tick,deg[N],tot,hd[N],lst[N],fst[N],ans[N],tag[N];
pii q[N];
vi pos[N],t[N];
struct edge {int to,nxt;} e[N];

int find(int x) {return nxt[x]==x?x:nxt[x]=find(nxt[x]);}
int dis(int x,int y) {
    if(x<y) return y-x;
    else return tick-x+y;
}
void del(int x) {nxt[x]=find(x%tick+1); tag[x]=0;}
void dfs1(int u) {for(int v:t[u]) if(v!=fa[u]) fa[v]=u, dfs1(v);}
int calc(int x,int y) {
    x+=y, x%=tick; if(x==0) x=tick;
    return dfn[x];
}
void dfs2(int u) {
    dfn[++tick]=u; pos[u].eb(tick); fst[u]=tick;
    for(int i=hd[u];i;i=e[i].nxt) {
        dfs2(e[i].to);
        dfn[++tick]=u; pos[u].eb(tick);
    }
}
void work(int p,int time,int qt) {
    int u=dfn[p];
    if(tag[p]) {
        for(int x:pos[u]) del(x);
        while(qt<=Q&&q[qt].fi==time) ans[q[qt].se]=u, qt++;
        if(t[u].size()==1) work(t[u][0],time+1,qt);
        else work(t[u][1],time+1,qt);
    } else {
        int np=find(p);
        if(!tag[np]) {
            while(qt<=Q) ans[q[qt].se]=calc(p,q[qt].fi-time), qt++;
            return;
        }
        int nt=time+dis(p,np);
        while(qt<=Q&&q[qt].fi<nt) ans[q[qt].se]=calc(p,q[qt].fi-time), qt++;
        work(np,nt,qt);
    }
}

signed main() {
    n=read(), Q=read();
    rep(i,1,n) {
        deg[i]=read();
        rep(j,1,deg[i]) t[i].eb(read());
    }
    dfs1(1);
    rep(i,1,n) {
        int pos=0;
        if(i!=1) {while(t[i][pos]!=fa[i]) pos++;}
        pos=(pos+1)%deg[i], hd[i]=tot+1;
        rep(j,1,deg[i]) {
            if(t[i][pos]==fa[i]) break;
            e[++tot]=(edge){t[i][pos],tot+1};
            pos=(pos+1)%deg[i];
        }
        if(hd[i]>tot) hd[i]=0;
        else e[tot].nxt=0;
    }
    dfs2(1); tick--;
    per(i,tick,1) {
        int u=dfn[i]; lst[u]=i;
        if(fst[u]==i) {
            for(int &x:t[u]) {
                if(!lst[x]) x=fst[x];
                else x=lst[x];
            }
        }
    }
    rep(i,1,Q) q[i].fi=read(), q[i].se=i;
    sort(q+1,q+Q+1);
    rep(i,1,tick) nxt[i]=i, tag[i]=1;
    work(1,0,1);
    rep(i,1,Q) printf("%lld\n",ans[i]);
    return 0;
}