HDU 4010 Query on The Trees(动态树)

题意

给定一棵 \(n\) 个节点的树,每个点有点权。完成 \(m\) 个操作,操作四两种,连接 \((x,y)\) ;提 \(x\) 为根,并断 \(y\) 与它的父节点;增加路径 \((x,y)\) 的节点一个 \(w\) 的点权;求路径 \((x,y)\) 的最大点权。

思路

基本概念介绍

\(\text{Link-Cut-Tree}\) 是一棵支持修改的树,以 \(\text{Splay}\) 为基础,均摊复杂度 \(O(n\log n)\) 的在线数据结构,支持的基础操作如下:

  • 连边

  • 断边

  • 换根

  • 路径修改

  • 路径查询

无根树中,换根是用来进行路径操作的,而有根树并不能进行路径操作(因为需要改变根)

本题维护一棵无根树,使用以上功能即可。

如果用的够熟练,还有以下拓展功能:

  • 有根树/基环树的处理
  • 维护边权
  • 维护最小生成树
  • 维护子树信息

\(\text{LCT}\) 的结构是若干棵 \(\text{splay}\) ,每一棵 \(\text{splay}\) 维护的是原树上的某一条链(从顶到下)的一个序列,特殊的,某一棵 \(\text{splay}\) 根的父亲是它维护的实链在原树上对应的父亲,然而这个父亲并没有这个子节点(即认父不认子)。

基本函数

rotate

void rotate(int x)
{
int y=fa[x],z=fa[y],k=(x==ch[y][1]);
if(!isroot(y))ch[z][y==ch[z][1]]=x; fa[x]=z;
ch[y][k]=ch[x][!k]; if(ch[x][!k])fa[ch[x][!k]]=y;
ch[x][!k]=y,fa[y]=x;
push_up(y),push_up(x);
}

其中 \(\text{isroot}\) 函数如下:

bool isroot(int x){return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];}

功能是判断这个点是不是 \(\text{splay}​\) 的根。

在 \(\text{splay}\) 里,上面的这些判断都可以略去,但是在 \(\text{LCT}\) 里不能略去。因为在 \(\text{LCT}\) 中,旋转是要在同一个 \(\text{splay}\) 中的,不能翻过头;而且零号节点有儿子可能会对 \(\text{isroot}\) 的判断有影响。

splay

void splay(int x)
{
stk[tp=1]=x;
for(int y=x;!isroot(y);y=fa[y])stk[++tp]=fa[y];
while(tp)push_down(stk[tp]),tp--;
while(!isroot(x))
{
int y=fa[x],z=fa[y];
if(!isroot(y))(x==ch[y][1])==(y==ch[z][1])?rotate(y):rotate(x);
rotate(x);
}
}

有两点不同,首先这里的 \(\text{splay}\) 函数只需要上旋至根,所以不用再传参数;然后是这个函数一般从底向上,即没有提前先找到要提到根的节点 \(x\) ,故需要提前 \(\text{down}\) 完一路上的节点。

access

\(\text{access}(x)\) 的作用是将从 \(x\) 节点到原树的根这条路径放在同一个 \(\text{splay}\) 中,即打通 \(x\) 到根的路径。

void access(int x)
{
for(int y=0;x;y=x,x=fa[x])
splay(x),ch[x][1]=y,push_up(x);
}

make_root

\(\text{make_root}(x)\) 用来将 \(x\) 提到根,它和上面的 \(\text{access}\) 都是 \(\text{LCT}\) 比较核心的部分,它的组成异常的简短。

void make_root(int x)
{
access(x),splay(x),reved(x);
}

\(\text{reved}\) 函数如下,表示旋转。

void reved(int x)
{
rev[x]^=1;
std::swap(ch[x][0],ch[x][1]);
}

将 \(x\) 与根放入同一个 \(\text{splay}\) 中,然后将 \(x\) 提到 \(\text{splay}\) 的根,由于然后对这个 \(\text{splay}\) 维护的序列进行翻转,不难发现,这样的旋转并不会使树的结构混乱,而恰好能将 \(x\) 作为根。

get_root

得到节点 \(x\) 的根,并将根也翻至 \(\text{splay}\) 的根。

int get_root(int x)
{
access(x),splay(x);
while(ch[x][0])push_down(x),x=ch[x][0];
splay(x);
return x;
}

link

\(\text{link}(x,y)\) 表示从 \(x\) 向 \(y\) 连一条边,如果 \(x,y\) 已经连通,则返回 \(\text{false}​\) 。

bool link(int x,int y)
{
make_root(x);
if(get_root(y)==x)return false;
fa[x]=y;
return true;
}

cut

\(\text{cut}(x,y)​\) 表示断开边 \((x,y)​\),如果 \(x,y​\) 没有连边,则返回 \(\text{false}​\) 。

bool cut(int x,int y)
{
make_root(x);
if(get_root(y)!=x||ch[x][1]!=y||ch[y][0])return false; //画图观察,三个条件缺一不可
ch[x][1]=fa[y]=0;
push_up(x);
return true;
}

lift(split)

个人习惯把它叫作 \(\text{lift}\) ,其中 \(\text{lift}(x,y)\) 表示将路径 \((x,y)\) 实化,提起,以 \(x\) 作为根,如果 \((x,y)\) 不连通,则返回 \(\text{false}\)。

bool lift(int x,int y)
{
make_root(x),access(y);
return get_root(y)==x;
}

这是路径操作之前的一句话,完成后可以在 \(x\) 节点上打标记修改,\(x\) 节点也维护了路径的信息。

这个东西实在是个大坑,难以一文讲通,这里给出这道模板题的代码。

代码

#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
const int N=3e5+5;
struct LinkCutTree
{
int ch[N][2],fa[N];bool rev[N];
int pw[N],Mx[N],tag[N];
int stk[N],tp;
void init(){create(0,0);}
void create(int x,int val)
{
ch[x][0]=ch[x][1]=fa[x]=rev[x]=0;
tag[x]=0;pw[x]=Mx[x]=val;
}
bool isroot(int x){return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];}
void reved(int x)
{
rev[x]^=1;
std::swap(ch[x][0],ch[x][1]);
}
void taged(int x,int val)
{
tag[x]+=val;
pw[x]+=val;
Mx[x]+=val;
}
void push_up(int x)
{
Mx[x]=std::max(std::max(Mx[ch[x][0]],Mx[ch[x][1]]),pw[x]);
}
void push_down(int x)
{
if(rev[x])
{
if(ch[x][0])reved(ch[x][0]);
if(ch[x][1])reved(ch[x][1]);
rev[x]=0;
}
if(tag[x])
{
if(ch[x][0])taged(ch[x][0],tag[x]);
if(ch[x][1])taged(ch[x][1],tag[x]);
tag[x]=0;
}
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=(x==ch[y][1]);
if(!isroot(y))ch[z][y==ch[z][1]]=x; fa[x]=z;
ch[y][k]=ch[x][!k]; if(ch[x][!k])fa[ch[x][!k]]=y;
ch[x][!k]=y,fa[y]=x;
push_up(y),push_up(x);
}
void splay(int x)
{
stk[tp=1]=x;
for(int y=x;!isroot(y);y=fa[y])stk[++tp]=fa[y];
while(tp)push_down(stk[tp]),tp--;
while(!isroot(x))
{
int y=fa[x],z=fa[y];
if(!isroot(y))(x==ch[y][1])==(y==ch[z][1])?rotate(y):rotate(x);
rotate(x);
}
}
void access(int x)
{
for(int y=0;x;y=x,x=fa[x])
splay(x),ch[x][1]=y,push_up(x);
}
void make_root(int x)
{
access(x),splay(x),reved(x);
}
int get_root(int x)
{
access(x),splay(x);
while(ch[x][0])push_down(x),x=ch[x][0];
splay(x);
return x;
}
int get_fa(int x)
{
access(x),splay(x);
if(!ch[x][0])return -1;
push_down(x);
x=ch[x][0];
while(ch[x][1])push_down(x),x=ch[x][1];
splay(x);
return x;
}
bool link(int x,int y)
{
make_root(x);
if(get_root(y)==x)return false;
fa[x]=y;
return true;
}
bool cut(int x,int y)
{
make_root(x);
if(get_root(y)!=x||ch[x][1]!=y||ch[y][0])return false;
ch[x][1]=fa[y]=0;
push_up(x);
return true;
}
bool lift(int x,int y)
{
make_root(x),access(y);
return get_root(y)==x;
}
void update(int x,int y,int val)
{
lift(x,y);
taged(x,val);
}
int query(int x,int y)
{
lift(x,y);
return Mx[x];
}
}LCT;
int n,m; int main()
{
while(~scanf("%d",&n))
{
LCT.init();
FOR(i,1,n)LCT.create(i,0);
FOR(i,1,n-1)
{
int u,v;
scanf("%d%d",&u,&v);
LCT.link(u,v);
}
FOR(i,1,n)
{
int x;
scanf("%d",&x);
LCT.update(i,i,x);
}
scanf("%d",&m);
while(m--)
{
int op,x,y,z;
scanf("%d",&op);
if(op==1)
{
scanf("%d%d",&x,&y);
if(!LCT.link(x,y))puts("-1");
}
else if(op==2)
{
scanf("%d%d",&x,&y);
if(x==y||!LCT.lift(x,y))puts("-1");
else
{
LCT.make_root(x);
LCT.cut(y,LCT.get_fa(y));
}
}
else if(op==3)
{
scanf("%d%d%d",&z,&x,&y);
if(!LCT.lift(x,y))puts("-1");
else LCT.update(x,y,z);
}
else if(op==4)
{
scanf("%d%d",&x,&y);
if(!LCT.lift(x,y))puts("-1");
else printf("%d\n",LCT.query(x,y));
}
}
puts("");
}
return 0;
}
上一篇:dom 笔记


下一篇:Java泛型总结---基本用法,类型限定,通配符,类型擦除