这篇文章讲的很好很详细，但是写了几天后发现似乎是挺残的版本。
2049: [Sdoi2008]Cave 洞穴勘测
3282: Tree
2002: [Hnoi2010]Bounce 弹飞绵羊
1036: [ZJOI2008]树的统计Count
都是基础操作吧
后来发现makeroot这个操作可以用个各个地方，改进了一下愉快的切
2631: tree
结果就是tle
结果就是调了两天用了三种lct中splay写法还是tle
结果就是不明白某大神友情提供的代码到底比我的程序优在哪……！
至今还是tle，但是换了几种写法 写法一（自己的程序+各种奇怪的优化+网上大众版splay) {$M 1000000000,0,maxlongint} //{$ inline in} type arr=record toward,next:longint; end; const maxn=100200; mm=51061; var a:array[1..4]of longint; st:string; fa,q,first,size:array[0..maxn]of longint; sum,mark1,mark2,value:array[0..maxn]of qword; c:array[0..maxn,0..1]of longint; rev:array[0..maxn]of boolean; edge:array[0..maxn*2]of arr; n,m,tot,u,v,j,k,i:longint; procedure prepare;//inline; var i,j,k:longint; begin st:=st+' '; i:=3; j:=0; while i<length(st) do begin inc(j); k:=i; while st[i]<>' ' do inc(i); val(copy(st,k,i-k),a[j]); inc(i); end; end; procedure swap(var x,y:longint);//inline; var i:longint; begin i:=x; x:=y; y:=i end; function isroot(x:longint):boolean; begin if (c[fa[x],0]=x) or (c[fa[x],1]=x) then exit(True); exit(false); end; procedure update(x:longint);//inline; begin sum[x]:=(sum[c[x,0]]+sum[c[x,1]]+value[x]) mod mm; size[x]:=size[c[x,0]]+size[c[x,1]]+1; end; procedure maintain(x,y,z:longint);//inline; begin if x=0 then exit; value[x]:=(value[x]*y+z) mod mm; sum[x]:=(sum[x]*y+z*size[x])mod mm; mark1[x]:=mark1[x]*y mod mm; mark2[x]:=(mark2[x]*y+z) mod mm end; procedure pushdown(x:longint);//inline; var l,r:longint; begin if x=0 then exit; if rev[x] then begin swap(c[x,0],c[x,1]); rev[c[x,1]]:=not rev[c[x,1]]; rev[c[x,0]]:=not rev[c[x,0]]; rev[x]:=false; end; if (mark1[x]<>1) or (mark2[x]<>0) then begin maintain(c[x,0],mark1[x],mark2[x]); maintain(c[x,1],mark1[x],mark2[x]); mark1[x]:=1; mark2[x]:=0; end end; procedure rotate(x:longint);//inline; var y,z,l,r:longint; begin y:=fa[x]; z:=fa[y]; if c[y,0]=x then l:=0 else l:=1; r:=l xor 1; if isroot(y) then if c[z,0]=y then c[z,0]:=x else c[z,1]:=x; fa[x]:=z; fa[y]:=x; fa[c[x,r]]:=y; c[y,l]:=c[x,r]; c[x,r]:=y; update(y); //update(x) end; procedure splay(x:longint);//inline; var top,i,y,z:longint; begin top:=1; q[1]:=x; i:=x; while isroot(i) do begin inc(top); q[top]:=fa[i]; i:=fa[i]; end; for i:=top downto 1 do pushdown(q[i]); while isroot(x) do begin y:=fa[x]; z:=fa[y]; if isroot(y) then if (c[y,0]=x) xor (c[z,0]=y) then rotate(x) else rotate(y); rotate(x); end end; function access(x:longint):longint;//inline; var y:longint; begin y:=0; repeat splay(x); c[x,1]:=y; fa[y]:=x; update(x); y:=x; x:=fa[x]; until x=0; exit(y); end; procedure makeroot(x:longint);//inline; var y:longint; begin y:=access(x); //splay(x); rev[y]:=not rev[y]; fa[y]:=0; end; procedure lct(x1,y1,x2,y2:longint);//inline; var y:longint; begin makeroot(x1); access(x1); y:=y1; while isroot(y) do y:=fa[y]; fa[y]:=0; y:=x2; while fa[y]<>0 do y:=fa[y]; if y<>x1 then swap(x2,y2); y:=access(y2); rev[y]:=not rev[y]; fa[y]:=x2 end; procedure addedge(j,k:longint);//inline; begin inc(tot); edge[tot].toward:=k; edge[tot].next:=first[j]; first[j]:=tot end; procedure dfs(x:longint);//inline; var i,too:longint; begin i:=first[x]; value[x]:=1; sum[x]:=1; mark1[x]:=1; size[x]:=1; while i<>0 do begin too:=edge[i].toward; if fa[x]<>too then begin fa[too]:=x; dfs(too); end; i:=edge[i].next; end end; begin readln(n,m); for i:=1 to n-1 do begin readln(j,k); addedge(j,k); addedge(k,j); end; dfs(n>>1); while m>0 do begin dec(m); readln(st); prepare; case st[1] of '*':begin //j:=j mod mm; makeroot(a[1]); //maintain1(access(a[2]),a[3]); maintain(access(a[2]),a[3],0); end; '+':begin //j:=j mod mm; makeroot(a[1]); //maintain2(access(a[2]),a[3]); maintain(access(a[2]),1,a[3]); end; '-':lct(a[1],a[2],a[3],a[4]); '/':begin makeroot(a[1]); writeln(sum[access(a[2])]); end; end; end; end. 写法二（yangzhe大神写法） type arr=record toward,next:longint; end; const maxn=100200; mm=51061; var a:array[1..4]of longint; st:string; fa,q,first,size,child:array[0..maxn]of longint; sum,mark1,mark2,value:array[0..maxn]of qword; c:array[0..maxn,0..1]of longint; rev:array[0..maxn]of boolean; edge:array[0..maxn*2]of arr; n,m,tot,u,v,j,k,i:longint; procedure prepare; var i,j,k:longint; begin st:=st+' '; i:=3; j:=0; while i<length(st) do begin inc(j); k:=i; while st[i]<>' ' do inc(i); val(copy(st,k,i-k),a[j]); inc(i); end; end; procedure swap(var x,y:longint); var i:longint; begin i:=x; x:=y; y:=i; end; procedure update(x:longint); begin sum[x]:=(sum[c[x,0]]+sum[c[x,1]]+value[x]) mod mm; size[x]:=size[c[x,0]]+size[c[x,1]]+1; end; procedure maintain(x,y,z:longint); begin if x=0 then exit; value[x]:=(value[x]*y+z) mod mm; sum[x]:=(sum[x]*y+z*size[x])mod mm; mark1[x]:=mark1[x]*y mod mm; mark2[x]:=(mark2[x]*y+z) mod mm end; procedure pushdown(x:longint); var l,r:longint; begin if x=0 then exit; if rev[x] then begin child[c[x,0]]:=1-child[c[x,0]]; child[c[x,1]]:=1-child[c[x,1]]; swap(c[x,0],c[x,1]); rev[c[x,1]]:=not rev[c[x,1]]; rev[c[x,0]]:=not rev[c[x,0]]; rev[x]:=false; end; if (mark1[x]<>1) or (mark2[x]<>0) then begin maintain(c[x,0],mark1[x],mark2[x]); maintain(c[x,1],mark1[x],mark2[x]); mark1[x]:=1; mark2[x]:=0; end end; procedure rotate(node,x:longint); var p,y,tmp:longint; begin p:=fa[node]; y:=child[p]; tmp:=fa[p]; fa[node]:=tmp; child[node]:=y; if y<>2 then c[tmp,y]:=node; y:=1-x; tmp:=c[node,y]; c[p,x]:=tmp; fa[tmp]:=p; child[tmp]:=x; fa[p]:=node; child[p]:=y; c[node,y]:=p; update(p); end; procedure splay(node:longint); var a,p,b,top:longint; begin top:=1; q[1]:=node; i:=node; while child[i]<>2 do begin inc(top); q[top]:=fa[i]; i:=fa[i]; end; for i:=top downto 1 do pushdown(q[i]); repeat a:=child[node]; if a=2 then break; p:=fa[node]; b:=child[p]; if a=b then rotate(p,a) else rotate(node,a); if b=2 then break; rotate(node,b); until false; update(node); end; function access(x:longint):longint; var y:longint; begin y:=0; repeat splay(x); child[c[x,1]]:=2; c[x,1]:=y; fa[y]:=x; child[y]:=1; update(x); y:=x; x:=fa[x]; until x=0; exit(y); end; procedure makeroot(x:longint); var y:longint; begin y:=access(x); rev[y]:=not rev[y]; fa[y]:=0; child[y]:=2; end; function getrt(x:longint):longint; begin while child[x]<>2 do x:=fa[x]; exit(x); end; function getup(x:longint):longint; begin while fa[x]<>0 do x:=fa[x]; exit(x); end; procedure lct(x1,y1,x2,y2:longint); var y:longint; begin makeroot(y1); access(y1); y:=getrt(x1); fa[y]:=0; child[y]:=2; if getup(x2)<>x1 then swap(x2,y2); y:=access(y2); rev[y]:=not rev[y]; fa[y]:=x2; child[y]:=2; end; procedure addedge(j,k:longint); begin inc(tot); edge[tot].toward:=k; edge[tot].next:=first[j]; first[j]:=tot end; procedure dfs(x:longint); var i,too:longint; begin i:=first[x]; value[x]:=1; sum[x]:=1; mark1[x]:=1; size[x]:=1; while i<>0 do begin too:=edge[i].toward; if fa[x]<>too then begin fa[too]:=x; child[too]:=2; dfs(too); end; i:=edge[i].next; end end; begin readln(n,m); for i:=1 to n-1 do begin readln(j,k); addedge(j,k); addedge(k,j); end; child[n>>1]:=2; dfs(n>>1); while m>0 do begin dec(m); readln(st); prepare; case st[1] of '*':begin //j:=j mod mm; makeroot(a[2]); //maintain1(access(a[1]),a[3]); maintain(access(a[1]),a[3],0); end; '+':begin //j:=j mod mm; makeroot(a[2]); //maintain2(access(a[1]),a[3]); maintain(access(a[1]),1,a[3]); end; '-':lct(a[1],a[2],a[3],a[4]); '/':begin makeroot(a[2]); writeln(sum[access(a[1])]); end; end; end; end.