HDU4010
类比静态区间问题->动态区间问题的拓展
我们这里把区间变成树，树上的写改删查问题，最最最常用LCT解决
LCT用来维护动态的森林，对于森林中的每一棵树，用Splay维护。
LCT是把这些Splay关联在一起的数据结构
我们以HDU4010为例子
int n,m,cnt,top;
bool rev[maxn];
int mx[maxn],fa[maxn],v[maxn],tag[maxn],last[maxn],q[maxn];
int c[maxn][];
struct edge{int to,next;}e[maxn<<];
这里把树存成了图，邻接表表示，对于森林中的每一棵树，用Splay来维护
mx,fa,v,tag,c和Splay相关，q是个栈用来预处理fa还有协助Splay操作（具体问题请参考本站Splay的那篇介绍）
这里树边为双向边，在遍历的时候注意判断
接下来介绍LCT中的一些概念和实现：
void access(int x)
{
for(int t=;x;t=x,x=fa[x])
splay(x),c[x][]=t,update(x);
}
这个access的意思是专门开辟一条从根到x的路径，将其作为“重链”，并使用Splay来进行维护
如果x往下是重边，就将其变成轻边，这样这条重链就独立出来了
void makeroot(int x)
{
access(x);splay(x);rev[x]^=;
}
这个makeroot的意思是把某一个节点变成整个LCT的根，这个操作配合access操作就可以方便地提取LCT任意两点之间的路径了
void link(int x,int y)
{
makeroot(x);fa[x]=y;
}
Link-Cut Tree中的link,这个的意思就是连接两棵LCT
void cut(int x,int y)
{
makeroot(x);access(y);splay(y);
c[y][]=fa[c[y][]]=;update(y);
}
这个的意思就是把一棵LCT分离成两棵LCT
还有一个find函数：
int find(int x)
{
access(x);splay(x);
while(c[x][]) x=c[x][];
return x;
}
作用类似于并查集，用来判断一个点到底在哪棵LCT上面
还有一个操作是把一条路径的点权增大val
void add(int x,int y,int val)
{
makeroot(x);access(y);splay(y);
tag[y]+=val;mx[y]+=val;v[y]+=val;
}
最后给出求路径上最值的方法：
makeroot(x);access(y);splay(y);printf("%d\n",mx[y]);
先把x提取到LCT的根，然后打通到y的路径，然后把y伸展到根直接查询mx[y]即可
我们在进行题目所描述的一系列操作的时候，是需要前提的
link操作只能连接两棵不同的LCT，否则树就不是树了
cut操作只能cut在同一棵LCT上否则没有意思
add操作也只能在同一棵LCT上进行
查询也是如此
其实，修改查询的操作都可以原生态地使用LCT的辅助树：Splay来完成
而对于树的动态操作，一定要借助于LCT的函数来完成
最后给出完整的代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=;
const int maxn=;
int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}
return x;
}
int n,m,cnt,top;
bool rev[maxn];
int mx[maxn],fa[maxn],v[maxn],tag[maxn],last[maxn],q[maxn];
int c[maxn][];
struct edge{int to,next;}e[maxn<<];
void insert(int u,int v)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void update(int x)
{
int l=c[x][],r=c[x][];
mx[x]=max(mx[l],mx[r]);
mx[x]=max(mx[x],v[x]);
}
void pushdown(int x)
{
int l=c[x][],r=c[x][];
if(rev[x])
{
rev[l]^=;rev[r]^=;rev[x]^=;
swap(c[x][],c[x][]);
}
if(tag[x])
{
if(l){tag[l]+=tag[x];mx[l]+=tag[x];v[l]+=tag[x];}
if(r){tag[r]+=tag[x];mx[r]+=tag[x];v[r]+=tag[x];}
tag[x]=;
}
}
bool isroot(int x)
{
return c[fa[x]][]!=x&&c[fa[x]][]!=x;
}
void rotate(int x)
{
int y=fa[x],z=fa[y],l,r;
if(c[y][]==x)l=;else l=;r=l^;
if(!isroot(y))
{
if(c[z][]==y)c[z][]=x;
else c[z][]=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);
}
void splay(int x)
{
top=;q[++top]=x;
for(int i=x;!isroot(i);i=fa[i])
q[++top]=fa[i];
while(top)pushdown(q[top--]);
while(!isroot(x))
{
int y=fa[x],z=fa[y];
if(!isroot(y))
{
if(c[y][]==x^c[z][]==y)rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x)
{
for(int t=;x;t=x,x=fa[x])
splay(x),c[x][]=t,update(x);
}
void makeroot(int x)
{
access(x);splay(x);rev[x]^=;
}
void link(int x,int y)
{
makeroot(x);fa[x]=y;
}
void cut(int x,int y)
{
makeroot(x);access(y);splay(y);
c[y][]=fa[c[y][]]=;update(y);
}
int find(int x)
{
access(x);splay(x);
while(c[x][]) x=c[x][];
return x;
}
void add(int x,int y,int val)
{
makeroot(x);access(y);splay(y);
tag[y]+=val;mx[y]+=val;v[y]+=val;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<=n;i++)
last[i]=tag[i]=rev[i]=fa[i]=c[i][]=c[i][]=;
mx[]=-INF;cnt=;
for(int i=;i<n;i++)
{
int u=read(),v=read();
insert(u,v);
}
for(int i=;i<=n;i++) mx[i]=v[i]=read();
q[++top]=;
for(int k=;k<=top;k++)
{
int now=q[k];
for(int i=last[now];i;i=e[i].next)
{
if(e[i].to!=fa[now])
{
fa[e[i].to]=now;
q[++top]=e[i].to;
}
}
}
m=read();
while(m--)
{
int opt=read(),x=read(),y=read(),w;
switch(opt)
{
case :
if(find(x)==find(y)) {puts("-1");break;}
link(x,y);break;
case :
if(find(x)!=find(y)||x==y) {puts("-1");break;}
cut(x,y);break;
case :
w=x;x=y;y=read();
if(find(x)!=find(y)) {puts("-1");break;}
add(x,y,w);break;
case :
if(find(x)!=find(y)){puts("-1");break;}
makeroot(x);access(y);splay(y);printf("%d\n",mx[y]);break;
}
}
puts("");
}
return ;
}
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=;
const int maxn=;
int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}
return x;
}
int n,m,cnt,top;
bool rev[maxn];
int mx[maxn],fa[maxn],v[maxn],tag[maxn],last[maxn],q[maxn];
int c[maxn][];
struct edge{int to,next;}e[maxn<<];
void insert(int u,int v)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void update(int x)
{
int l=c[x][],r=c[x][];
mx[x]=max(mx[l],mx[r]);
mx[x]=max(mx[x],v[x]);
}
void pushdown(int x)
{
int l=c[x][],r=c[x][];
if(rev[x])
{
rev[l]^=;rev[r]^=;rev[x]^=;
swap(c[x][],c[x][]);
}
if(tag[x])
{
if(l){tag[l]+=tag[x];mx[l]+=tag[x];v[l]+=tag[x];}
if(r){tag[r]+=tag[x];mx[r]+=tag[x];v[r]+=tag[x];}
tag[x]=;
}
}
bool isroot(int x)
{
return c[fa[x]][]!=x&&c[fa[x]][]!=x;
}
void rotate(int x)
{
int y=fa[x],z=fa[y],l,r;
if(c[y][]==x)l=;else l=;r=l^;
if(!isroot(y))
{
if(c[z][]==y)c[z][]=x;
else c[z][]=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);
}
void splay(int x)
{
top=;q[++top]=x;
for(int i=x;!isroot(i);i=fa[i])
q[++top]=fa[i];
while(top)pushdown(q[top--]);
while(!isroot(x))
{
int y=fa[x],z=fa[y];
if(!isroot(y))
{
if(c[y][]==x^c[z][]==y)rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x)
{
for(int t=;x;t=x,x=fa[x])
splay(x),c[x][]=t,update(x);
}
void makeroot(int x)
{
access(x);splay(x);rev[x]^=;
}
void link(int x,int y)
{
makeroot(x);fa[x]=y;
}
void cut(int x,int y)
{
makeroot(x);access(y);splay(y);
c[y][]=fa[c[y][]]=;update(y);
}
int find(int x)
{
access(x);splay(x);
while(c[x][]) x=c[x][];
return x;
}
void add(int x,int y,int val)
{
makeroot(x);access(y);splay(y);
tag[y]+=val;mx[y]+=val;v[y]+=val;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<=n;i++)
last[i]=tag[i]=rev[i]=fa[i]=c[i][]=c[i][]=;
mx[]=-INF;cnt=;
for(int i=;i<n;i++)
{
int u=read(),v=read();
insert(u,v);
}
for(int i=;i<=n;i++) mx[i]=v[i]=read();
q[++top]=;
for(int k=;k<=top;k++)
{
int now=q[k];
for(int i=last[now];i;i=e[i].next)
{
if(e[i].to!=fa[now])
{
fa[e[i].to]=now;
q[++top]=e[i].to;
}
}
}
m=read();
while(m--)
{
int opt=read(),x=read(),y=read(),w;
switch(opt)
{
case :
if(find(x)==find(y)) {puts("-1");break;}
link(x,y);break;
case :
if(find(x)!=find(y)||x==y) {puts("-1");break;}
cut(x,y);break;
case :
w=x;x=y;y=read();
if(find(x)!=find(y)) {puts("-1");break;}
add(x,y,w);break;
case :
if(find(x)!=find(y)){puts("-1");break;}
makeroot(x);access(y);splay(y);printf("%d\n",mx[y]);break;
}
}
puts("");
}
return ;
}
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=;
const int maxn=;
int read()
{
int x=;char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}
return x;
}
int n,m,cnt,top;
bool rev[maxn];
int mx[maxn],fa[maxn],v[maxn],tag[maxn],last[maxn],q[maxn];
int c[maxn][];
struct edge{int to,next;}e[maxn<<];
void insert(int u,int v)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void update(int x)
{
int l=c[x][],r=c[x][];
mx[x]=max(mx[l],mx[r]);
mx[x]=max(mx[x],v[x]);
}
void pushdown(int x)
{
int l=c[x][],r=c[x][];
if(rev[x])
{
rev[l]^=;rev[r]^=;rev[x]^=;
swap(c[x][],c[x][]);
}
if(tag[x])
{
if(l){tag[l]+=tag[x];mx[l]+=tag[x];v[l]+=tag[x];}
if(r){tag[r]+=tag[x];mx[r]+=tag[x];v[r]+=tag[x];}
tag[x]=;
}
}
bool isroot(int x)
{
return c[fa[x]][]!=x&&c[fa[x]][]!=x;
}
void rotate(int x)
{
int y=fa[x],z=fa[y],l,r;
if(c[y][]==x)l=;else l=;r=l^;
if(!isroot(y))
{
if(c[z][]==y)c[z][]=x;
else c[z][]=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);
}
void splay(int x)
{
top=;q[++top]=x;
for(int i=x;!isroot(i);i=fa[i])
q[++top]=fa[i];
while(top)pushdown(q[top--]);
while(!isroot(x))
{
int y=fa[x],z=fa[y];
if(!isroot(y))
{
if(c[y][]==x^c[z][]==y)rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x)
{
for(int t=;x;t=x,x=fa[x])
splay(x),c[x][]=t,update(x);
}
void makeroot(int x)
{
access(x);splay(x);rev[x]^=;
}
void link(int x,int y)
{
makeroot(x);fa[x]=y;
}
void cut(int x,int y)
{
makeroot(x);access(y);splay(y);
c[y][]=fa[c[y][]]=;update(y);
}
int find(int x)
{
access(x);splay(x);
while(c[x][]) x=c[x][];
return x;
}
void add(int x,int y,int val)
{
makeroot(x);access(y);splay(y);
tag[y]+=val;mx[y]+=val;v[y]+=val;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<=n;i++)
last[i]=tag[i]=rev[i]=fa[i]=c[i][]=c[i][]=;
mx[]=-INF;cnt=;
for(int i=;i<n;i++)
{
int u=read(),v=read();
insert(u,v);
}
for(int i=;i<=n;i++) mx[i]=v[i]=read();
q[++top]=;
for(int k=;k<=top;k++)
{
int now=q[k];
for(int i=last[now];i;i=e[i].next)
{
if(e[i].to!=fa[now])
{
fa[e[i].to]=now;
q[++top]=e[i].to;
}
}
}
m=read();
while(m--)
{
int opt=read(),x=read(),y=read(),w;
switch(opt)
{
case :
if(find(x)==find(y)) {puts("-1");break;}
link(x,y);break;
case :
if(find(x)!=find(y)||x==y) {puts("-1");break;}
cut(x,y);break;
case :
w=x;x=y;y=read();
if(find(x)!=find(y)) {puts("-1");break;}
add(x,y,w);break;
case :
if(find(x)!=find(y)){puts("-1");break;}
makeroot(x);access(y);splay(y);printf("%d\n",mx[y]);break;
}
}
puts("");
}
return ;
}