关于树论【动态树问题（LCT）】
搬运：看一道caioj1439
题目描述
一开始给你一棵n个点n-1条边的树，每个点有一个权值wi。
三种操作：
op=1 u v :在点u和点v之间建一条边。
op=2 u v:摧毁点u到点v之间的边。
op=3 w u v:将点u和点v之间路径上的点（包括u,v），权值增加w。
op=4 u v:询问点u到点v之间路径上的点（包括u,v），权值最大值。
当操作违法时（询问一中u,v已经相连，二三四中u,v不联通，一二操作u==v）不进行操作并输出-1。
输入
从文件weight.in中读取输入。
第1行为1个正整数n，表示点的个数。
第2~n行为开始树所有的边，每行两个正整数u,v，代表u和v之间有一条边。
第n+1行有n个正整数，表示一开始点的权值。
下一行为一个正整数m代表下来有m个操作。
以下m行，一行表示一个操作。
行首先输入一个正整数op。
当op=1,2,4时，输入两个正整数u,v
当op=3时，输入三个正整数w,u,v
操作如题意
输出
输出到文件weight.out。
对每个4操作，输出点u到点v之间路径上的点（包括u,v），权值最大值。同时对于违法情况输出-1。
该类动态树问题一个突出点就是动态，假如没有1、2操作当然可以方便的运用树链剖分算法水过（详见第8章 树链剖分）。前一章的伸展树只支持改变树的形态，难以对树的结构进行改变，对于建边删边的操作的需要，我们要运用多棵伸展树组成新树，即解决该类动态树问题的普遍方法，Link-Cut-Tree，俗称LCT。
它跟树链剖分类似，只不过树剖用线段树维护重链，而LCT用伸展树（是不是很高大上），在两棵伸展树之间，如果它们属于同一个LCT，那么将有一条虚边，连接着它们，在不影响伸展树的正常操作前提上，保持应有的连系。
大家可以感性的认识….可以假设一开始问题给出的树边都是虚边，我们人为的在上面画重链，每条重链用一棵伸展树维护他（就跟线段树一个道理嘛，目标是减少暴力枚举的时间，只不过伸展树更加快捷灵活），关键的，如果没有连边删边操作，同伸展树一样，整棵树的结构是不变的。
当然啦，题目也可能给出很多棵树，我们可以臆想一下，这些树都属于0节点的子树，只不过他们连的边被“操作删除”了，这样也是合理的。同样道理，当我们在解决动态树问题的过程中，有时也会出现这棵树被分成多份。也就是说，Link-Cut-Tree本质上这个图可以是一个森林。
讲讲操作吧。
最重要的access(x)：令x到当前所处的树的根这条路径成为偏爱路径(相当于树剖的重链)，然后用splay维护，这是与树剖最大的不同，这样的灵活性也符合动态树。
make_root(x)：令x成为当前树的根，但是！！不是在当前重链中伸展树的根，也不是整个图中所有点的根，而是，x当前所处的树的根！ 由于 LCT的Link和Cut操作，注定了整个图可能出现多棵树，树与树之间如果不添加边，都是一个独立的动态树。
Link(x,y)：让x成为根，然后连一条虚边到y就OK了。
Cut(x,y)：先将x设为根（假设现在是点1）假设y是点6，那我们将1~6的路径设为偏爱路径（放在一棵伸展树里）将6旋转到伸展树的根，可以发现，点1肯定在伸展树的最左端，让y断开与左端的连接就行了。 
findroot(x)：同理，真正在树中的根肯定在树的最左边，所以说找根其实很简单。
PS：所以在make_root后要让整棵伸展树翻转，比如说将6变为根，1,4都在它左边，这样就不科学了。
如果还有不明白的，可以看caioj的书，还有上caioj1439看视频，视频非常好！！出视频的人改变了我的一生，从未见过有如此懂我的人，他太强了，我崇拜他一辈子！！
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{
int f,d,c,n,son[],mx,ad;
bool fz;
}tr[];
void add(int x)
{
tr[x].d+=tr[x].ad;tr[x].mx+=tr[x].ad;
int lc=tr[x].son[],rc=tr[x].son[];
tr[lc].ad+=tr[x].ad;
tr[rc].ad+=tr[x].ad;
tr[x].ad=;
}
void update(int x)
{
int lc=tr[x].son[],rc=tr[x].son[];
tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
if(tr[lc].ad!=)add(lc);
if(tr[rc].ad!=)add(rc);
if(lc==)tr[lc].mx=;
if(rc==)tr[rc].mx=;
tr[x].mx=max(max(tr[lc].mx,tr[rc].mx),tr[x].d);
}
void reverse(int x)
{
tr[x].fz=false;
swap(tr[x].son[],tr[x].son[]);
int lc=tr[x].son[],rc=tr[x].son[];
tr[lc].fz=-tr[lc].fz;
tr[rc].fz=-tr[rc].fz;
}
void rotate(int x,int w)
{
int f=tr[x].f,ff=tr[f].f;
int R,r; R=f;r=tr[x].son[w];
tr[R].son[-w]=r;
if(r!=)tr[r].f=R; R=ff;r=x;
if(tr[R].son[]==f)tr[R].son[]=r;
else if(tr[R].son[]==f)tr[R].son[]=r;
tr[r].f=R; R=x;r=f;
tr[R].son[w]=r;
tr[r].f=R; update(f);
update(x);
}
int tmp[];
void splay(int x,int rt)
{
int s=,i=x;
while(tr[i].f!=&&(tr[tr[i].f].son[]==i||tr[tr[i].f].son[]==i))
{
tmp[++s]=i;
i=tr[i].f;
}
tmp[++s]=i;
while(s!=)
{
i=tmp[s];s--;
if(tr[i].fz==true)reverse(i);
if(tr[i].ad!=)add(i);
} while(tr[x].f!=rt&&(tr[tr[x].f].son[]==x||tr[tr[x].f].son[]==x))//还有虚边啊！
{
int f=tr[x].f,ff=tr[f].f;
if(ff==rt||(tr[ff].son[]!=f&&tr[ff].son[]!=f))
{
if(x==tr[f].son[])rotate(x,);
else rotate(x,);
}
else
{
if(tr[f].son[]==x&&tr[ff].son[]==f){rotate(f,);rotate(x,);}
else if(tr[f].son[]==x&&tr[ff].son[]==f){rotate(x,);rotate(x,);}
else if(tr[f].son[]==x&&tr[ff].son[]==f){rotate(x,);rotate(x,);}
else if(tr[f].son[]==x&&tr[ff].son[]==f){rotate(f,);rotate(x,);}
}
}
}
int n,w[];
void make_tree()
{
for(int i=;i<=n;i++)
{
tr[i].f=;
tr[i].mx=tr[i].d=w[i];
tr[i].c=;tr[i].n=;
tr[i].son[]=tr[i].son[]=;
tr[i].fz=false;tr[i].ad=;
}
}
void access(int x)//访问x
//还记得树剖的重儿子吗？这是令点x到整棵动态树的根这条路径变成偏爱路径(相当于树剖的重链)，这一条路径就是一棵伸展树。
{
int y=;
while(x!=)
{
splay(x,);
tr[x].son[]=y;
if(y!=)tr[y].f=x;
y=x;x=tr[x].f;
}
}
void makeroot(int x)//让x成为当前树的根
{
access(x);splay(x,);//因为是链，splay之后只有左孩子(上面y=0)
tr[x].fz=-tr[x].fz;//因为要让x成为整棵树的根，所以x的深度要最小(通过翻转实现),为find_root做准备
}
void link(int x,int y)
{//为什么可以直接用makeroot？？因为判断过x和y的find_root 是否相同，不相同表示x和y是不联通的
makeroot(x);tr[x].f=y;access(x);//删去access是没有影响的，但从定义上说应该加上
}
void cut(int x,int y)
{
makeroot(x);
access(y);splay(y,);
tr[tr[y].son[]].f=;tr[y].son[]=;
update(y);
}
int find_root(int x)//访问完x后，x所属的伸展树的最左端的点就是所在树真正的根，因为伸展树实际意义上就是一条链啊！！
{
access(x);splay(x,);
while(tr[x].son[]!=)x=tr[x].son[];
return x;
}
void increase(int x,int y,int W)//令x，y处于一棵伸展树，y为根，由于是链，直接更新y的ad就行了
{
makeroot(x);
access(y);splay(y,);
tr[y].ad+=W;
}
int findmax(int x,int y)//同理，这也是一样的
{
makeroot(x);
access(y);splay(y,);
update(y);return tr[y].mx;
}
struct edge
{
int x,y;
}e[];
int main()
{
freopen("weight.in","r",stdin);
freopen("weight.out","w",stdout);
int m,op,x,y,W;
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<n;i++)scanf("%d%d",&e[i].x,&e[i].y);
for(int i=;i<=n;i++)scanf("%d",&w[i]);
make_tree();
for(int i=;i<n;i++)
link(e[i].x,e[i].y);
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d",&op);
if(op==)
{
scanf("%d%d",&x,&y);
if(find_root(x)==find_root(y)||x==y)
printf("-1\n");
else
link(x,y);
}
else if(op==)
{
scanf("%d%d",&x,&y);
if(find_root(x)!=find_root(y)||x==y)
printf("-1\n");
else
cut(x,y);
}
else if(op==)
{
scanf("%d%d%d",&W,&x,&y);
if(find_root(x)!=find_root(y))
printf("-1\n");
else
increase(x,y,W);
}
else
{
scanf("%d%d",&x,&y);
if(find_root(x)!=find_root(y))
printf("-1\n");
else
printf("%d\n",findmax(x,y));
}
}
printf("\n");
}
return ;
}
最新文章
- Git的.gitignore文件配置
- KinerCode.js
- C语言中的复合类型
- Arbitrage---poj2240（floyd）
- ［翻译］The Neophyte's Guide to Scala Part 12: Type Classes
- 第三百四十七天 how can I 坚持
- webx学习笔记
- Web---文件上传-用apache的工具处理、打散目录、简单文件上传进度
- ScheduleThreadPoolExecutor源码分析
- Node.js 和Socket.IO 实现chat WEBIM
- js中赋值表达式的值为右边
- HDU 1043 Eight (BFS&#183;八数码&#183;康托展开)
- 《转载》最新鲜最详细的Android SDK下载安装及配置教程
- 基于USB网卡适配器劫持DHCP Server嗅探Windows NTLM Hash密码
- C# 给一个控件去掉焦点
- linux 下mysql服务的管理
- Android如何在一个TextView中实现多种文本风格？
- Effective Java 第三版——59. 熟悉并使用Java类库
- C# 读写文件摘要
- Delphi：Exception输出堆栈信息