链接

　　https://www.luogu.org/problem/show?pid=3637

题解

　　对边操作的LCT，把边化成点，然后操作。

　　这道题目从a到b和从b到a是不一样的，所以在reverse的时候要将权值乘-1。

代码

//LCT #include <cstdio> #include <algorithm> #define maxn 500000 using namespace std; int N, M, K, Q; struct node { int rev, w, sum; node *f, *ch[2]; }nd[maxn], *s[maxn]; inline int getwh(node *x) {if(!x->f)return -1;if(x->f->ch[0]==x)return 0;if(x->f->ch[1]==x)return 1;return -1;} inline bool isroot(node *x){return getwh(x)==-1;} inline void join(node *x, node *y, int wh){if(x)x->f=y;if(y)y->ch[wh]=x;} inline void rev(node *x){if(x)x->rev^=1;} inline void pushdown(node *x) { if(!x)return; if(x->rev) { x->w=-x->w;x->sum=-x->sum;swap(x->ch[0],x->ch[1]); rev(x->ch[0]),rev(x->ch[1]); x->rev=0; } } inline void pushup(node *x) { pushdown(x->ch[0]),pushdown(x->ch[1]); x->sum=x->w; if(x->ch[0])x->sum+=x->ch[0]->sum; if(x->ch[1])x->sum+=x->ch[1]->sum; } inline void rotate(node *x) { node *y=x->f, *z=y->f; int c=getwh(x); if(isroot(y))x->f=y->f;else join(x,z,getwh(y)); join(x->ch[!c],y,c),join(y,x,!c); pushup(y);pushup(x); } inline void splay(node *x) { node *y; int top=0; for(y=x;!isroot(y);y=y->f)s[++top]=y;s[++top]=y; for(;top;top--)pushdown(s[top]); while(!isroot(x)) { y=x->f; if(isroot(y)){rotate(x);return;} if(getwh(x)^getwh(y))rotate(x);else rotate(y); rotate(x); } } inline void access(node *x) { node *t=0; while(x) { splay(x); x->ch[1]=t; pushup(x); t=x,x=x->f; } } inline void makeroot(node *x){access(x);splay(x);rev(x);} inline void link(node *x, node *y){makeroot(x);x->f=y;} inline void cut(node *x, node *y) { makeroot(x);access(y);splay(y); if(y->ch[0]==x and !x->ch[1])x->f=y->ch[0]=0; } inline node* findroot(node *x) { while(x->f)x=x->f; return x; } int main() { int a, b, c, i, t; node *x, *y, *z; scanf("%d%d%d%d",&N,&M,&K,&Q); for(i=1;i<=M;i++) { scanf("%d%d%d",&a,&b,&c); x=nd+N+i; x->w=x->sum=c%K; link(x,nd+a),link(x,nd+b); } for(i=1;i<=Q;i++) { scanf("%d%d%d",&t,&a,&b); if(t==1) { scanf("%d",&c); x=nd+N+M+i; x->w=x->sum=c%K; link(x,nd+a);link(x,nd+b); } if(t==2) { x=nd+a, y=nd+b; makeroot(x), access(y), splay(y); if(y->ch[0]!=x)z=y->ch[0];else z=x->ch[1]; if(!z)continue; if(z->ch[0] or z->ch[1])continue; cut(x,z),cut(y,z); } if(t==3) { scanf("%d",&c); if(findroot(nd+a)!=findroot(nd+b)){printf("-1\n");continue;} makeroot(nd+a),access(nd+b),splay(nd+b); printf("%d\n",((nd[b].sum+c)%K+K)%K); } } return 0; }