这两题都是link cut tree的裸题
之前看Qtree的论文，只会在确定父子关系的情况下连边和删边
如果在任意两个点连边删边怎么做呢？
这时候我们不能随意的将一个点的父节点设为另一个点，因为其中某个点的父节点可能已经被设为另外某点了
其实很简单，连边的时候，我们只要把x变成其所在原树的根，这样x是没有父节点了
然后把x的父节点设为y即可，删边、询问路径的道理类似，具体见程序
给出的是bzoj2631的程序
const mo=; var fa,q,a,mul,add,size,sum:array[..] of longint;
rev:array[..] of boolean;
son:array[..,..] of longint;
i,x0,y0,x,y,z,n,m,t:longint;
ch:char; function root(x:longint):boolean; //判断是Auxiliary tree（splay）上的父节点还是path parent
begin
exit((son[fa[x],]<>x) and (son[fa[x],]<>x));
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; procedure update(x:longint);
var l,r:longint;
begin
l:=son[x,];
r:=son[x,];
size[x]:=(size[l]+size[r]+) mod mo;
sum[x]:=(a[x]+sum[l]+sum[r]) mod mo;
end; procedure calc(x,c,j:longint);
begin
if (c<=) then //常数优化，少用int64
begin
mul[x]:=mul[x]*c mod mo;
add[x]:=(add[x]*c+j) mod mo;
sum[x]:=(sum[x]*c+int64(j)*int64(size[x])) mod mo;
a[x]:=(a[x]*c+j) mod mo;
end
else begin
mul[x]:=int64(mul[x])*int64(c) mod mo;
add[x]:=(int64(add[x])*int64(c)+j) mod mo;
sum[x]:=(int64(sum[x])*int64(c)+int64(j)*int64(size[x])) mod mo;
a[x]:=(int64(a[x])*int64(c)+j) mod mo;
end;
end; procedure push(x:longint);
begin
if rev[x] then
begin
rev[son[x,]]:=not rev[son[x,]];
rev[son[x,]]:=not rev[son[x,]];
swap(son[x,],son[x,]);
rev[x]:=false;
end;
if (mul[x]<>) or (add[x]<>) then
begin
if son[x,]<> then calc(son[x,],mul[x],add[x]);
if son[x,]<> then calc(son[x,],mul[x],add[x]);
mul[x]:=;
add[x]:=;
end;
end; procedure rotate(x,w:longint);
var y:longint;
begin
y:=fa[x];
if not root(y) then
begin
if son[fa[y],]=y then son[fa[y],]:=x
else son[fa[y],]:=x;
end;
fa[x]:=fa[y];
son[y,-w]:=son[x,w];
if son[x,w]<> then fa[son[x,w]]:=y;
son[x,w]:=y;
fa[y]:=x;
update(y);
end; procedure splay(x:longint);
var y,t,i:longint;
ff:boolean;
begin
t:=;
i:=x;
while not root(i) do
begin
inc(t);
q[t]:=i;
i:=fa[i];
end;
inc(t);
q[t]:=i;
for i:=t downto do
push(q[i]);
ff:=true;
if t= then exit;
while ff do
begin
y:=fa[x];
if y=q[t] then
begin
if son[y,]=x then rotate(x,)
else rotate(x,);
ff:=false;
end
else begin
if fa[y]=q[t] then ff:=false;
if son[fa[y],]=y then
begin
if son[y,]=x then rotate(y,)
else rotate(x,);
rotate(x,);
end
else begin
if son[y,]=x then rotate(x,)
else rotate(y,);
rotate(x,);
end;
end;
end;
update(x);
end; procedure access(x:longint);
var y:longint;
begin
y:=;
repeat
splay(x);
son[x,]:=y;
update(x); //这里要记得维护
y:=x;
x:=fa[x];
until x=;
end; procedure makeroot(x:longint);
begin
access(x); //执行access之后，x和当前树的根之间的路径构成Auxiliary tree
splay(x); //将x旋到Auxiliary tree的根，这时候x没有右孩子，左子树的点都是x的祖辈
rev[x]:=not rev[x]; //执行翻转操作，这时候x是Auxiliary tree上最小的点，也就变成了原树的根
end; procedure link(x,y:longint);
begin
makeroot(x);
fa[x]:=y;
end; procedure cut(x,y:longint);
begin
makeroot(x);
access(y);
splay(y);
son[y,]:=;
fa[x]:=;
end; procedure path(x,y:longint); //构成x到y的路径
begin
makeroot(x);
access(y); //x到y路径上的点就在一棵Auxiliary tree中
splay(y);
end; begin
readln(n,m);
for i:= to n do
begin
a[i]:=;
size[i]:=;
sum[i]:=;
mul[i]:=;
end;
for i:= to n- do
begin
readln(x,y);
link(x,y);
end;
for i:= to m do
begin
read(ch);
if ch='+' then
begin
readln(x,y,z);
z:=z mod mo;
path(x,y);
calc(y,,z);
end
else if ch='-' then
begin
readln(x0,y0,x,y);
cut(x0,y0);
link(x,y);
end
else if ch='*' then
begin
readln(x,y,z);
z:=z mod mo;
path(x,y);
calc(y,z,);
end
else begin
readln(x,y);
path(x,y);
writeln(sum[y]);
end;
end;
end.