爱悠闲 > Link-Cut Tree

Link-Cut Tree

分类: 数据结构  |  标签: LinkCutTree,数据结构  |  作者: delayyy 相关  |  发布日期 : 2014-11-27  |  热度 : 1192°

Link-Cut Tree是一种解决动态树问题的数据结构。

动态树问题,大概也就是要动态维护树的路径上的一些信息之类的。

 

定义操作节点Acs,无实义,但对树的形态会造成影响。

其基本思想是动态的树链剖分,每个节点向其最后Acs的子树引一条P边,连续的P边组成P链,这样整棵树便被剖成了许多P链。

对于每条P链,根据深度用Splay维护之,并在Splay的根记录其最浅节点所连点,即为虚边。至此,整棵树成了很多坨Splay和一些虚边。

 

<1>链剖分

便于快速和维护路径信息。

 

<2>Splay

(话说Splay是个愉悦而又神奇的东西,数列信息维护的神器啊!)

之所以用Splay维护,是因为它:

1.能快速得到或更改区间信息。

2.能快速分裂与合并。

3.十分愉♂悦。(无视这条 = =

 

<3>Acs操作

可以说是Link-Cut Tree的操作核心了,几乎所有操作都离不开这个基本操作。也正是这个操作,控制着全局的形态。

设对点v进行一次Acs操作。脑补一下,结果应该是v到根的路径被打通成一条P链。

考虑变化:这条从v通往根的P链上的所有点,原来的P边都应该消失。

Acs Code:

void Access(int d)
{
  int u=d, v=0;
  do{
    Splay(u);
    o[c[u][1]]=1, c[u][1]=v, f[v]=u, o[v]=0;
    Update(u);
    v=u, u=f[u];
  }while(u);
} 
// 形象地来说,就说一路往上打通,剪枝合并剪枝合并……直到根。



 

 



同类文章:数据结构