Solution

对于每个链维护两个信息，到链底部的最近白点和到链顶部的最近白点。需要对子树的信息进行维护。

由于左右子树交换会更改点信息，因此不能使用 makeroot。

在不能使用 makeroot 的情况下，不能使用 link。因此需要预处理整棵树的形状。即直接设置虚父亲即可。

Code

// Code by ajcxsu
// Problem: query on the tree V

#include<bits/stdc++.h>
using namespace std;

#define INF (0x3f3f3f3f)
const int N=1e5+10;
struct Node *nil;
struct Node {
    Node *ch[2], *f; 
    int ma, mab, s, c, col, id;
    multiset<int> ima;
    Node(int i=-1) { id=i, ma=mab=0x3f3f3f3f; ch[0]=ch[1]=f=nil; col=0; s=c=1; }
    bool nroot() { return f->ch[0]==this || f->ch[1]==this; }
    int dir() { return nroot()?f->ch[1]==this:-1; }
    void upd() {
        ma=min({ch[0]->ma, (col?ch[0]->s:INF), ch[1]->ma+1+ch[0]->s});
        if(ima.size()) ma=min(ma, *(ima.begin())+1+ch[0]->s);
        ma=min(ma, INF);

        mab=min({ch[1]->mab, (col?ch[1]->s:INF), ch[0]->mab+1+ch[1]->s});
        if(ima.size()) mab=min(mab, *(ima.begin())+1+ch[1]->s);
        mab=min(mab, INF);
        assert((ma==INF)==(mab==INF));
        s=c+ch[0]->s+ch[1]->s;
    }
    int query() {
        assert(ch[1]==nil);
        return min((ima.size()?*(ima.begin())+1:INF), mab);
    }
} *nd[N];
void ini() {
    nil=new Node();
    nil->ch[0]=nil->ch[1]=nil->f=nil, nil->s=nil->c=0;
}

void rot(Node *x) {
    Node *y=x->f, *z=y->f;
    int d=x->dir();
    y->ch[d]=x->ch[!d]; if(x->ch[!d]!=nil) x->ch[!d]->f=y;
    x->f=z; if(y->dir()!=-1) z->ch[y->dir()]=x;
    x->ch[!d]=y, y->f=x, y->upd();
}
void splay(Node *x) {
    Node *y;
    while(x->nroot()) {
        y=x->f;
        if(!y->nroot()) rot(x);
        else if(y->dir()==x->dir()) rot(y), rot(x);
        else rot(x), rot(x);
    }
    x->upd();
}
void access(Node *x) {
    Node *y=nil;
    while(x!=nil) {
        splay(x);
        if(y!=nil) x->ima.erase(x->ima.find(y->ma));
        x->ima.insert(x->ch[1]->ma);
        x->ch[1]=y;
        x->upd(), y=x, x=x->f;
    }
}
int findroot(Node *x) {
    access(x), splay(x);
    while(x->ch[0]!=nil) x=x->ch[0];
    return x->id;
}
void makeroot(Node *x) {
    access(x), splay(x);
}

template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar();
}
template<typename T, typename ...Args> inline void gn(T &x, Args &...args) { gn(x), gn(args...); }

int n;
int h[N], to[N<<1], nexp[N<<1], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
void dfs(int x, int fr) {
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr) {
            dfs(to[u], x);
            nd[to[u]]->f=nd[x];
            nd[x]->ima.insert(INF);
        }
}

int main() {
    ini(); for(int i=0; i<N; i++) nd[i]=new Node(i);
    gn(n);
    int u, v;
    for(int i=0; i<n-1; i++) gn(u, v), ins(u, v), ins(v, u);
    int q; gn(q);
    dfs(1, 0);
    while(q--) {
        gn(u, v);
        if(!u) makeroot(nd[v]), nd[v]->col^=1, nd[v]->upd();
        else {
            makeroot(nd[v]);
            int res;
            printf("%d\n", (res=nd[v]->query())<INF?res:-1);
        }
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/spoj-qtree5.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆