【题解】Query on a tree III LCT SPOJ2798

第一个操作显然是不要考虑的……

考虑第二个操作怎么办 (实际上是超级 easy 的)

每个节点维护一个值 sum，表示 $Splay$ 中它子树的和，每个点的权值为 1(黑)0(白)。

对于这个操作，我们可以先 $split(1,x)$ ，现在 x 是这个 $Splay$ 的根。我们将要找的就是这颗 $Splay$ 中深度最小的为黑点的节点。

找 Answer 之前先特判一下 s[x]是否大于 0，如果为 0，直接跳过即可。

不然进入循环，分三种情况：

• 1. 如果 s[ch[x][0]]大于 0，说明有更优的答案 (左子树深度小于 x)，x=ch[x][0]。
• 2. 否则，如果 x 本身就是黑点，那么 x 就是答案了，直接 break。
• 3. 不然，如果 x 到 1 的节点都是白色，那就只能去 x 的右子树找了，x=ch[x][1]。

退出循环时 x 即为答案，输出即可。

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
#define A printf("A") 
using namespace std;
const int N=1e5+2;
int n,m,f[N],s[N],v[N],r[N],ch[N][2];
template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}
inline int chk(int x){return ch[f[x]][1]==x;}
inline int isroot(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
inline void pushup(int x){s[x]=s[ch[x][0]]+s[ch[x][1]]+v[x];}
inline void pushdown(int x){
    if(!r[x])return;r[x]=0;
    r[ch[x][0]]^=1,r[ch[x][1]]^=1,swap(ch[x][0],ch[x][1]);
}
inline void Splay_push(int x)
{if(isroot(x))Splay_push(f[x]);pushdown(x);}
inline void rotate(int x){
    int y=f[x],z=f[y],k=chk(x),v=ch[x][!k];
    if(isroot(y))ch[z][chk(y)]=x;ch[x][!k]=y,ch[y][k]=v;
    if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y);
}
inline void Splay(int x){
    int y=x;Splay_push(x);
    while(isroot(x)){
        if(isroot(y=f[x]))
           rotate((ch[y][0]==x)^(ch[f[y]][0]==y)?x:y);
        rotate(x); 
    }pushup(x);return;
}
inline void Access(int x){
    for(register int y=0;x;x=f[y=x])
       Splay(x),ch[x][1]=y,pushup(x); 
}
inline int findroot(int x){
    Access(x);Splay(x);
    while(ch[x][0])pushdown(x),x=ch[x][0];
    Splay(x);return x;
}
inline void makeroot(int x){Access(x);Splay(x);r[x]^=1;}
inline void split(int x,int y){makeroot(x);Access(y);Splay(y);}
inline void link(int x,int y){makeroot(x);if(findroot(x)!=findroot(y))f[x]=y;}
inline void cut(int x,int y){split(x,y);if(findroot(y)==x&&f[x]==y&&!ch[x][1])f[x]=ch[y][0]=0;}
int main(){
    IN(n),IN(m);
    for(register int x,y,i=1;i<n;++i)
    {IN(x),IN(y);link(x,y);}
    for(register int op,x,i=1;i<=m;++i){
        IN(op),IN(x);
        if(op==0){
            makeroot(x);v[x]^=1;pushup(x);
        }else if(op==1){
            split(1,x);
            if(!s[x]){printf("-1\n");continue;}
            while(s[x]){
                pushdown(x);
                if(s[ch[x][0]])x=ch[x][0];
                else if(v[x])break;
                else x=ch[x][1];
            }printf("%d\n",x);
        }
    }return 0;
}

听说是树剖的题目诶，LCT 水过也没多大问题吧…….(主要是 LCT 练手)