Query on a tree again! SPOJ

https://www.luogu.org/problemnew/show/P4116
一个log（LCT）比两个log（树剖）慢到不知道哪里去系列。。。
  1 #pragma GCC optimize("Ofast")
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<vector>
  6 using namespace std;
  7 #define fi first
  8 #define se second
  9 #define mp make_pair
 10 #define pb push_back
 11 typedef long long ll;
 12 typedef unsigned long long ull;
 13 typedef pair<int,int> pi;
 14 
 15 namespace LCT
 16 {
 17 struct Node
 18 {
 19     Node *ch[2],*fa;
 20     bool rev;
 21     bool d;Node *dd;
 22     int id;
 23     void upd()
 24     {
 25         if(ch[0]&&ch[0]->dd)    dd=ch[0]->dd;
 26         else if(d)    dd=this;
 27         else dd=ch[1]?ch[1]->dd:0;
 28     }
 29     void pd()
 30     {
 31         if(rev)
 32         {
 33             swap(ch[0],ch[1]);
 34             if(ch[0])    ch[0]->rev^=1;
 35             if(ch[1])    ch[1]->rev^=1;
 36             rev=0;
 37         }
 38     }
 39 }nodes[300100];
 40 int mem;
 41 Node *getnode()
 42 {
 43     return nodes+(mem++);
 44 }
 45 bool isroot(Node *x)
 46 {
 47     return (!x->fa)||((x->fa->ch[0]!=x)&&(x->fa->ch[1]!=x));
 48 }
 49 bool gson(Node *o)    {return o==o->fa->ch[1];}
 50 void rotate(Node *o,bool d)
 51 {
 52     Node *k=o->ch[!d];if(!isroot(o))    o->fa->ch[gson(o)]=k;
 53     o->ch[!d]=k->ch[d];k->ch[d]=o;
 54     o->upd();k->upd();
 55     k->fa=o->fa;o->fa=k;if(o->ch[!d])    o->ch[!d]->fa=o;
 56 }
 57 Node *st[300100];int top;
 58 void solvetag(Node *o)
 59 {
 60     while(!isroot(o))    st[++top]=o,o=o->fa;
 61     st[++top]=o;
 62     while(top)    st[top--]->pd();
 63 }
 64 void splay(Node *o)
 65 {
 66     solvetag(o);
 67     Node *fa,*fafa;bool d1,d2;
 68     while(!isroot(o))
 69     {
 70         fa=o->fa;d1=(o==fa->ch[0]);
 71         if(isroot(fa))    rotate(fa,d1);
 72         else
 73         {
 74             fafa=o->fa->fa;d2=(fa==fafa->ch[0]);//要保证fa不是root之后才能获取这两个值，曾错过
 75             if(d1==d2)    rotate(fafa,d1),rotate(fa,d1);//zig-zig，两次相同方向的单旋，先把父亲转上去，再把自己转上去
 76             else    rotate(fa,d1),rotate(fafa,d2);//zig-zag，两次相反方向的单旋，连续两次把自己转上去
 77         }
 78     }
 79 }
 80 void access(Node *o)
 81 {
 82     for(Node *lst=NULL;o;lst=o,o=o->fa)
 83     {
 84         splay(o);//此处不pushdown是由于splay中保证进行过了
 85         o->ch[1]=lst;o->upd();//注意upd
 86     }
 87 }
 88 Node *gtop(Node *o)
 89 {
 90     access(o);splay(o);
 91     for(;o->ch[0];o=o->ch[0],o->pd());//此处不在开始前pushdown(o)是由于splay中保证进行过了
 92     splay(o);return o;//听说这里不splay一下也很难卡掉
 93 }
 94 void mtop(Node *o)    {access(o);splay(o);o->rev^=1;}
 95 void link(Node *x,Node *y)
 96 {
 97     if(gtop(x)==gtop(y))    return;
 98     mtop(y);y->fa=x;
 99 }
100 void cut(Node *x,Node *y)
101 {
102     mtop(x);access(y);splay(y);
103     if(y->ch[0]!=x||x->ch[1])    return;//如果x、y之间直接有边，那么上面一行的操作之后应当是x与y在单独一棵splay中，那么一定保证y左子节点是x且x没有右子节点
104     x->fa=y->ch[0]=NULL;//注意，改的是x的父亲和y的子节点(虽然x的确是树的根，但是此时在splay上是y的子节点，不能搞混)
105     y->upd();//注意
106 }
107 void change(Node *y)
108 {
109     access(y);splay(y);
110     y->d^=1;y->upd();
111 }
112 int query(Node *x,Node *y)
113 {
114     mtop(x);access(y);splay(y);
115     return y->dd?y->dd->id:-1;
116 }
117 }
118 LCT::Node *nd[300100];
119 int n,q;
120 int main()
121 {
122     int i,idx,x,a,b;
123     scanf("%d%d",&n,&q);
124     for(i=1;i<=n;i++)    nd[i]=LCT::getnode(),nd[i]->id=i;
125     for(i=1;i<n;i++)
126     {
127         scanf("%d%d",&a,&b);
128         LCT::link(nd[a],nd[b]);
129     }
130     while(q--)
131     {
132         scanf("%d%d",&idx,&x);
133         if(idx==0)    LCT::change(nd[x]);
134         else    printf("%d
",LCT::query(nd[1],nd[x]));
135     }
136     return 0;
137 }