只有前四个操作的话就是LCT裸题了
链翻转不也是LCT的基本操作吗....
等等，翻转的是权值？
正常的翻转改的是各个点的深度，位置与权值的对应关系并没有改变
那么我们可以考虑维护两棵LCT，一棵维护形态，一棵维护位置
翻转其中一个就相当于改变了对应关系
说的不是很明白的啊....还是看看学姐的blog吧
代码如下：
#include<ctype.h>
#include<cstdio>
#define int long long
#define INF 2147483647000000l
#define N 50020
using namespace std;
typedef long long LL;
inline int read(){int x=0,f=1;char c;do c=getchar(),f=c=='-'?-1:f; while(!isdigit(c));do x=(x<<3)+(x<<1)+c-'0',c=getchar(); while(isdigit(c));return x*f;
}
inline int Max(int a,int b){return a>b?a:b;}
inline int Min(int a,int b){return a<b?a:b;}
inline int max3(int a,int b,int c){return Max(a,Max(b,c));}
inline int min3(int a,int b,int c){return Min(a,Min(b,c));}
int n,m,root,x,y,k,top;
int fir[N];
char c[13];
struct Edge{int to,nex;Edge(){}Edge(int _,int __):to(_),nex(__){}
}nex[N<<1];
inline void add(int x,int y){nex[++top]=Edge(y,fir[x]);fir[x]=top;
}
struct Node{Node *ch[2],*fa,*nex;int sum,minn,maxx,addv,x,siz;bool rev;Node();inline void Pushdown();inline void Add(int);inline void Reverse();inline void maintain(){minn=min3(ch[0]->minn,ch[1]->minn,x);maxx=max3(ch[0]->maxx,ch[1]->maxx,x);sum=ch[0]->sum+ch[1]->sum+x;siz=ch[0]->siz+ch[1]->siz+1;return;}inline int dir(){if(fa->ch[0]==this) return 0;if(fa->ch[1]==this) return 1;return -1;}
}*null,*p[N];
inline void Swap(Node *&a,Node *&b){static Node *c;c=a;a=b;b=c;}
Node::Node(){x=addv=minn=maxx=sum=rev=0;siz=1;ch[0]=ch[1]=nex=fa=null;return;
}
inline void Node::Pushdown(){if(addv){ch[0]->Add(addv);ch[1]->Add(addv);}if(rev) ch[0]->Reverse(),ch[1]->Reverse();if(nex!=null){if(ch[0]!=null) ch[0]->nex=nex;if(ch[1]!=null) ch[1]->nex=nex;}addv=rev=0;
}
inline void Node::Add(int k){if(this==null) return;addv=addv+k;sum=sum+k*siz;x+=k;minn+=k;maxx+=k;return;
}
inline void Node::Reverse(){if(this==null) return;Swap(ch[0],ch[1]);rev=!rev;return;
}
inline void init(){null=new Node;null->ch[0]=null->ch[1]=null->fa=null->nex=null;null->sum=null->x=null->siz=null->addv=null->rev=0;null->minn=INF;null->maxx=-INF;return;
}
void PushUp(Node *x){if(~x->dir()) PushUp(x->fa);x->Pushdown();return;
}
inline Node *K_th(Node *x,int k){if(x==null) return x;x->Pushdown();if(x->ch[0]->siz+1==k)return x;if(k<=x->ch[0]->siz) return K_th(x->ch[0],k);else return K_th(x->ch[1],k-x->ch[0]->siz-1);
}
inline void Rotate(Node *x,int d){static Node *k;static int di;k=x->ch[d^1];x->ch[d^1]=k->ch[d];if(x->ch[d^1]!=null) x->ch[d^1]->fa=x;k->ch[d]=x;if(~(di=x->dir())) x->fa->ch[di]=k;k->fa=x->fa;x->fa=k;x->maintain();k->maintain();return;
}
inline void Splay(Node *x){static int d;PushUp(x);while(~(d=x->dir())){if(x->fa->dir()==d)Rotate(x->fa->fa,d^1);Rotate(x->fa,d^1);}return;
}
inline void Splay_(Node *x,Node *&y){Splay(x);Splay(x->nex);y=K_th(x->nex,x->ch[0]->siz+1);Splay(y);return;
}
void dfs(int x,int fa){p[x]=new Node;p[x]->nex=new Node;p[x]->fa=p[fa];p[x]->nex->fa=p[fa]->nex;for(int i=fir[x];i;i=nex[i].nex){if(nex[i].to==fa) continue;dfs(nex[i].to,x);}
}
inline void Access(Node *x){static Node *pre,*pre_,*x_;pre=pre_=x_=null;while(x!=null){Splay_(x,x_);x->nex=x_;x->ch[1]->nex=x_->ch[1];x->ch[1]=pre;x_->ch[1]=pre_;pre_->fa=x_;x->maintain();x_->maintain();pre=x;pre_=x_;x=x->fa;}return;
}
inline void MakeRoot(Node *x){static Node *k;Access(x);Splay_(x,k);x->Reverse();k->Reverse();return;
}
inline Node *Extract(Node *x,Node *y){static Node *y_;MakeRoot(x);Access(y);Splay_(y,y_);return y_;
}
main(){init();n=read();m=read();root=read();for(register int i=1;i<n;i++){x=read();y=read();add(x,y);add(y,x);}p[0]=null;dfs(root,0);for(register int i=1;i<=m;i++){scanf("%s",c+1);x=read();y=read();if(c[3]=='c') k=read(),Extract(p[x],p[y])->Add(k);else if(c[3]=='m') printf("%lld\n",Extract(p[x],p[y])->sum);else if(c[3]=='j') printf("%lld\n",Extract(p[x],p[y])->maxx);else if(c[3]=='n') printf("%lld\n",Extract(p[x],p[y])->minn);else Extract(p[x],p[y])->Reverse();}return 0;
}