题目：

第二道LCT！

直接看TJ……

把连边表示成与点相连 是很好的。因为splay中的边变动得挺随意的。

感觉理解又加深了。那个query的部分，效果是x和y所在的辅助树中x深度最小、y深度最大，即当前辅助树就是x和y之间的链！

因为忘记在splay的最后pshp，RE（为什么是RE？）了好久。

#include
     
      #include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int N=5e4+5,M=1e5+5,INF=0x7fffffff;int n,m,pre[N+M],mx[N+M],c[N+M][2],fa[N],stack[N+M],top,val[N+M],ans;//val    //bool rev[N+M];struct Ed{    int x,y,a,b;    bool operator<(const Ed &k)const        {
    return a
         
          val[mx[x]])mx[x]=mx[c[x][0]];    if(val[mx[c[x][1]]]>val[mx[x]])mx[x]=mx[c[x][1]];}void reverse(int x){    if(rev[x]){        rev[c[x][0]]^=1;rev[c[x][1]]^=1;        swap(c[x][0],c[x][1]);        rev[x]=0;    }}void rotate(int x){    int y=pre[x],z=pre[y],d=(x==c[y][1]);    if(!isroot(y))c[z][y==c[z][1]]=x;    pre[x]=z;pre[y]=x;    c[y][d]=c[x][!d];pre[c[x][!d]]=y;c[x][!d]=y;    pshp(y);pshp(x);}void splay(int x){    stack[top=1]=x;    for(int t=x;!isroot(t);t=pre[t])stack[++top]=pre[t];    for(;top;top--)reverse(stack[top]);    for(;!isroot(x);rotate(x))    {        int y=pre[x],z=pre[y];        if(isroot(y))continue;        ((c[y][0]==x)^(c[z][0]==y))?rotate(x):rotate(y);    }    pshp(x);//}void access(int x){    for(int t=0;x;c[x][1]=t,t=x,x=pre[x])splay(x);}void makeroot(int x){    access(x);splay(x);rev[x]^=1;}int query(int x,int y){    makeroot(x);access(y);splay(y);//y没有右儿子     //access之后相当于在辅助树中splay，故不用rev //    printf("x=%d y=%d c[x][0]=%d c[x][1]=%d c[y][0]=%d c[y][1]=%d\n",x,y,c[x][0],c[x][1],c[y][0],c[y][1]);    return mx[y];    //x和y之间的不应该是x的右儿子？//    int vmx=mx[c[x][1]];    //此时应该是y为根、无右儿子；x为y的左儿子，无左儿子。故。 //    if(val[vmx]