这篇文章讲的很好很详细，但是写了几天后发现似乎是挺残的版本。

 

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
      
       ' ' 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:=iend;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 mmend;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;  endend;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);  endend;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]:=x2end;procedure addedge(j,k:longint);//inline;begin  inc(tot);  edge[tot].toward:=k;  edge[tot].next:=first[j];  first[j]:=totend;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;  endend;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
       
        ' ' 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 mmend;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;  endend;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]:=totend;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;  endend;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.