图书馆网站建设与评价研究,织梦cms 学校网站模板,wordpress公司门户,东莞营销网站建设哪家好文章目录LCT概念模板rotatoisrootsplayaccessmakerootsplitfindrootlinkcut封装版例题题目code普通版code封装版这篇博客主要是帮助大家理解各个模板及LCTLCTLCT的意思#xff0c;方便理解#xff0c;模板写法的理解在代码里有注释详解#xff0c;如果要看原理的话#xff…
文章目录LCT概念模板rotatoisrootsplayaccessmakerootsplitfindrootlinkcut封装版例题题目code普通版code封装版这篇博客主要是帮助大家理解各个模板及LCTLCTLCT的意思方便理解模板写法的理解在代码里有注释详解如果要看原理的话有很多写得好的博客我就不跟着大众的步伐前进了咱们要另辟蹊径 写完后发现皇宫其实就是皇帝和太子的乱来而且太子妃好像还是另外国家的皇帝或者皇帝继承人 那不都是男的。。。
LCT概念
等价映射 事实上, 所有解决动态树问题的方法, 归根结底都使用等价映射的基本思想 即, 将任意形态的树(原树)映射到度限制, 深度平均的新树(辅助树)上. Link-Cut Tree是由Sleator、Tarjan等科学家提出的一种实现动态树的数据结构 接下来皇宫生存法则开始啦(≧▽≦)/为了方便大家区分以下的这种文字都是表示皇宫三十六计生存法则的理解带入
Link-Cut Tree的若干概念 原树(represented trees)是若干有根树组成的森林每棵树与标准的有根树无异只不过增加了一个“优先(preference)”的概念
也就是一个大背景的前提在这个辉煌的皇宫内部最初始的树的根我们理解为皇帝 一个结点可能“偏好(prefer)”某个儿子使它成为“优先儿子(preferred child)” 皇室继承者太子 不得不说真的是一个昏君啊不用贤明的儿子却用偏心的儿子当太子 类似于树链剖分中的“重儿子” 优先儿子与它父亲之间的边称为“优先边(preferred edge)” 有什么好处皇帝都先考虑自己宠爱的儿子 类似于“重边”仅由优先边组成的路径称为“优先路径(preferredpath)” 太子只能有一个也就只能宠爱一个 类似于“重链”优先路径有可能只有一个结点被宠爱的子孙后代构成的庞大家族体系 需要注意的是用树链剖分的对应概念来类比只是帮助大家尽快理解Link-Cut Tree中引入的新概念 两者的区别是显著的重儿子、重边、重链等是静态的而优先关系是动态的随时可能变化 但是皇宫法则是动态变换的说不定哪一天你就被打入冷宫甚至国都灭亡了 通常我们遇到的问题都是在原树上的 那些吃了雄心豹子胆的人生怕皇帝忘了还有他们的存在在皇帝眼皮子底下乱来甚至敢分裂出不同王朝 因此我们首先搞清楚在原树上要执行的是什么特定操作然后解释这个操作在Link-Cut Tree上怎样执行
Link-Cut Tree定义如下 路径树(path tree )是用来表示原树上的优先路径的树。路径树用splay tree实现你可以把一棵splay理解为一个王朝结点是原树的一条优先路径上所有结点并以结点在原树上的深度为关键字 为了解决这个庞大的家族体系因为皇帝说不定会忘记自己生了那么多儿子宠了那么多妃子但是他必须要让整个皇宫都在他的掌握范围内这个时候大臣就特别贴心的帮他理了一份家族关系而且深入研究发现各个之间的亲密程度一五一十都汇报给了皇帝他也不恼任着子孙们乱来只要别把国搞没了就行是啊~自己都被子孙挤下去了国也分散了
路径树也叫辅助树(Auxiliary Tree)大王朝在昏君的执政下成功解体 Link-Cut tree的核心思想是把原树剖分成若干优先路径然后把每条优先路径用一棵对应的路径树表示 每一个相互亲近的人成为一个团体彼此互帮互助也因为彼此之间的不团结将大王朝分成了多个王朝产生了多个不同的皇帝更绝的是彼此之间互不干涉永不往来留一条丝表示还有血缘关系哪天心情一好就把对方吞并了
准确地说原树剖分后是一组辅助树森林。多个王朝每一个王朝都有一个能力强的皇帝形成了各自的皇宫用着统一的皇宫规则 每棵路径树的根结点v对应王朝的皇帝都有一个“路径-父亲(path-parent)”指针指向原树上对应优先路径中最高结点的父结点u它的父亲有可能在另一个王朝是最低等/中等/皇帝的地位。但u的儿子指针并不指向v他的父亲可能忘记了自己儿子是另外一个王朝的皇帝还是宠信着跟自己在同一个王朝的唯一儿子(利用这一性质可以省略path-parent指针也是认父不认子)儿子认着自己的父亲想讨好自己的父亲让自己跟父亲在同一个王朝放着自己的皇位不坐你搞peach吗还真是孝顺呢 每个人都有自己想讨好的对象而且吊死在一棵树上但是被讨好的人也十分嚣张跋扈不稀罕 原树与辅助树的关系 箭头的有向边表示path-parent指针 一个复杂的例子皇宫家族分裂王朝体系 左图是原树红边表示优先路径每个爸爸宠幸的一个儿子 右图是辅助树。虚线表示path-parent指针 注意右图的单个结点也是一棵辅助树
对于一个 splaysplaysplay 而言按照中序遍历在原树上先遍历的是后遍历的祖先。 看似二叉实际上在原树上每个 splaysplaysplay 都是一条链。 原树中的重链 - 辅助树中结点们位于同一棵Splay中 尽管可能自己孤家寡人一个也可以建立只有一个人的空王朝然后去吞并其它王朝嘛 原树中的轻边 - 辅助树中子结点所在Splay的根节点的pathparent指向父结点 原树与辅助树的结构并不相同。原树是多叉的而辅助树是二叉排序树。 辅助树的根节点 ≠ 原树的根节点 辅助树中的path-parent ≠ 原树中的fa 由于要维护的信息已经都在辅助树中维护了所以LCT无需维护原树只维护辅助树即可. 原树已经被拆解成一条一条的重链表达成一组辅助树森林。 轻边和重链并不是固定的随着算法的进行轻链和重链随算法需要和题目要求而变化然而无论怎么变化由这棵辅助树一定能生成原树并满足辅助树的所有性质. 如果你懵了不用担心这很正常而且前面的废话也没有多少用你直接跳过都行只要把模板整好了 你就已经很可以了 但是你至少要知道虚边是一棵splaysplaysplay的根连出去连到另一个splaysplaysplay里面的某一点 一条条虚边把王朝牵扯到了一起方便自己想吞并其它王朝时自己方便和被吞并时对方方便聪明啊
模板 rotato
旋转操作我将其亲切地尊称为在自己的王朝里面合理地篡位可能是争夺当太监当宠妃...争夺当皇帝我的天胆子挺大啊
void rotate ( int x ) { int fa tree[x].f; int Gfa tree[fa].f;int k ( tree[fa].son[1] x );if ( isroot ( fa ) )//因为虚边是一棵splay的根连出去 剩下的自己内部交换是无影响的 所以一定要判断 tree[Gfa].son[tree[Gfa].son[1] fa] x;tree[x].f Gfa; tree[fa].son[k] tree[x].son[k ^ 1];if ( tree[x].son[k ^ 1] )tree[tree[x].son[k ^ 1]].f fa;tree[x].son[k ^ 1] fa;tree[fa].f x;update ( fa );update ( x );
}isroot
判断是否为根其名曰在你所在的王朝里面看你是不是穿着黄袍的皇上
bool isroot ( int x ) {//判断x是否为splay的根 return tree[tree[x].f].son[0] x || tree[tree[x].f].son[1] x;
}//如果连的是虚边那么它的父亲的儿子里面就没有它 splay
将点变成splay的根可以说是和rotate一起帮助它篡位成功的宦官心腹一路上绝杀成为皇帝该王朝要变天啦
void splay ( int x ) {//所有操作的目标都是该splay的根int Top 0, y x;st[ Top] y;//手打栈暂存当前点到根的整条路径 pushdown时要从上往下放标记while ( isroot ( y ) )st[ Top] y tree[y].f;while ( Top )pushdown ( st[Top -- ] );while ( isroot ( x ) ) {int fa tree[x].f, Gfa tree[fa].f;if ( isroot ( fa ) )( ( tree[Gfa].son[0] fa ) ^ ( tree[fa].son[0] x ) ) ? rotate ( x ) : rotate ( fa );rotate ( x );}
}access
将x与根打通使之同在一个splay 叫做争夺嫡系皇位继承人 成为最小的已经确定的皇位继承人把自己的兄弟挤出去且它很贪心子孙后代都还没确定选谁做自己的继承人想多当一会皇帝继承人当然这是不可能很快就被挤下去了。我实在不能理解为什么这个人不直接篡位当皇帝非要把一路上的亲戚都买通一起当皇位继承人 接着盗一波图实在画得太好了 绿色的表示一个splaysplaysplay这个LCTLCTLCT不是唯一的也有其他划分方案 我们要打通A−NA-NA−N每个爸爸宠信的儿子都可能会发生改变王朝里的成员随时都在发生着改变进行着吞并和分裂 篡位要一步一步来先让N成为他们小王朝的皇帝 接着跟自己的爸爸搞好关系以表尊重把自己的王朝都一起搭了进去当做嫁妆 用花言巧语哄骗他宠爱自己成为他的第一继承人我怎么感觉像是妃子争宠而不是儿子争位呢 用自己的爸爸去哄骗自己的爷爷这样爸爸当了第一继承人自己也会获得此王朝皇位的继承权了你为啥不直接冲上去啊搞啥子地下情 最后不知不觉间跟皇帝成了一个王朝的人还帮皇帝吞并其它王朝分裂势力给皇帝都搞懵了它还是很聪明的在最下面操作着一切一家族都跟着篡位而不是他一个人单枪匹马闯上去不仅会让皇帝无语而且也不会让自己的家族势力眼红因为他们都是第一继承人实在是妙啊
void access ( int x ) {for ( int son 0;x;son x, x tree[x].f ) {splay ( x );tree[x].son[1] son;update ( x );//儿子变了 要及时上传修改信息 }
}makeroot
换根亦或者正大光明地发动政变开始篡位成为新的皇帝这个时候管他三七二十一自己的手下势力已经足够强大叫什么来着...√富可敌国不服给我憋着老子就是能当皇帝而且这个国家都被颠倒了老皇帝成了最卑微的娃
void reverse ( int x ) {swap ( tree[x].son[0], tree[x].son[1] );//翻转一下使得所有点的深度都倒过来了 tree[x].flag ^ 1;//flag为翻转标记
}
void MakeRoot ( int x ) {//将x换成原树的根 access ( x );//x成为整个splay里面深度最深的点 splay ( x );//此splay里面的所有点都在x左边reverse ( x );
}split
求两点之间的路径别称太子与其它王朝的皇位继承人甚至是皇帝偷偷摸摸小花园 为什么是太子呢看我们的模板就是太子为了不被判通敌叛国乱搞罪决心发动政变当了皇上后就理所应当的两国联姻喜结连理然后就可以通过小花园路上所有人走向他啦赶脚像是偶像剧里面的光芒万丈时刻男主等着男主踏着日光带着旁人的艳羡给他一切
void split ( int x, int y ) {//拉出x-y的路径成为一个splay 此处写法把y变成splay的根 MakeRoot ( x );access ( y );//打通x-y 两个就在一个splay里面了 y是深度最深的 splay ( y );//此时y的左子树就是x-y路径了且y没有右子树
}findroot
找根绰号皇室继承人寻找自己现在所在王朝到底是哪个在做皇帝方便以后篡位 这个寻找方式也是没谁了先把自己跟该王朝的皇帝打通然后自己篡位当皇帝最后在一直往下面走去找变成卑微小生的老皇帝说我知道你是皇帝了你回来吧我以后再篡位够可以够不要脸
int FindRoot ( int x ) {//找到x所在原树的树根 access ( x );splay ( x );while ( tree[x].son[0] ) {pushdown ( x );x tree[x].son[0];}splay ( x );return x;
}link
连边理解为皇室继承人与自己的心上人确定关系之际 但是再怎么也不能乱伦所以必须先判断一下相爱的两人是否在同一个王朝里面有祖孙关系发现相爱后一个人成了自己的爸爸我把你当挚爱你竟然想当我爸爸
void link ( int x, int y ) {//连一条x-y的边 此处写法x的父亲指向y MakeRoot ( x );if ( FindRoot ( y ) x )//两点已经在同一子树中 不能再连边 return;tree[x].f y;/*如果题目保证连边合法 代码可简化为 MakeRoot ( x );tree[x].fa y;*/
} cut
断边含义皇室继承人刚刚确定关系就狠心抛弃以往的宠妃爸爸期待着下一个新欢爸爸但是这不能皇室继承人自己yy必须两人是彼此确认直系关系了的
void cut ( int x, int y ) {//将x-y的边断开 MakeRoot ( x );if ( FindRoot ( y ) ! x || tree[y].f ! x || tree[y].son[0] )return;//x在findroot(y)后重新转到了根tree[y].f tree[x].son[1] 0;update ( x );//少了个儿子 要及时更新 /*x-y之间有边要满足连通性(在同一个splay) 存在父子关系 y没有左儿子因为access(y)后 假如x-y在同一splay中而没有直接连边 那么这条路径上就一定有其他的点在中序遍历时会位于x-y之间那么可能y的父亲不是x 或者 y的父亲是x 其它的点就在y左子树里 *//*如果维护了size还可以换法判断 因为access后按道理应该只有x-y两个点if( FindRoot ( y ) ! x || tree[x].siz 2 )return;*//*如果题目保证断边合法 可以简化为split ( x, y );tree[x].fa tree[y].son[0] 0;update ( y );*/
}封装版
namespace LCT {struct node { int son[2], fa, tag; }t[maxn];bool root( int x ) { return t[t[x].fa].son[0] ^ x and t[t[x].fa].son[1] ^ x; }void reverse( int x ) { swap( t[x].son[0], t[x].son[1] ); t[x].tag ^ 1; }void pushdown( int x ) {if( ! t[x].tag ) return;if( t[x].son[0] ) reverse( t[x].son[0] );if( t[x].son[1] ) reverse( t[x].son[1] );t[x].tag ^ 1;}void rotate( int x ) {int fa t[x].fa;int Gfa t[fa].fa;int d t[fa].son[1] x;if( ! root( fa ) ) t[Gfa].son[t[Gfa].son[1] fa] x;t[x].fa Gfa;if( t[x].son[d ^ 1] ) t[t[x].son[d ^ 1]].fa fa;t[fa].son[d] t[x].son[d ^ 1];t[x].son[d ^ 1] fa;t[fa].fa x;}void splay( int x ) {sta[ top] x; int y x;while( ! root( y ) ) sta[ top] y t[y].fa;while( top ) pushdown( sta[top --] );while( ! root( x ) ) {int fa t[x].fa, Gfa t[fa].fa;if( ! root( fa ) ) (t[Gfa].son[0] fa) ^ (t[fa].son[0] x) ? rotate( x ) : rotate( fa );rotate( x ); }}void access( int x ) { for( int son 0;x;son x, x t[x].fa ) splay( x ), t[x].son[1] son; }void makeroot( int x ) { access( x ); splay( x ); reverse( x ); }void split( int x, int y ) { makeroot( x ); access( y ); splay( y ); }void link( int x, int y ) { makeroot( x ); t[x].fa y; }void cut( int x, int y ) { split( x, y ); t[x].fa t[y].son[0] 0; }int findroot( int x ) { access( x ); splay( x ); while( t[x].son[0] ) pushdown( x ), x t[x].son[0]; splay( x ); return x; }bool check( int x, int y ) { makeroot( x ); return findroot( y ) x; }
}例题
题目
爪⑧dbq我爪巴
code普通版
#include cstdio
#include iostream
using namespace std;
#define maxn 300005
struct node {int f, val, sum, flag, son[2];
}tree[maxn];
int n, m;
int st[maxn];void reverse ( int x ) {swap ( tree[x].son[0], tree[x].son[1] );tree[x].flag ^ 1;
}void update ( int x ) {tree[x].sum tree[tree[x].son[0]].sum ^ tree[tree[x].son[1]].sum ^ tree[x].val;
}void pushdown ( int x ) {if ( tree[x].flag ) {if ( tree[x].son[0] )reverse ( tree[x].son[0] );if ( tree[x].son[1] )reverse ( tree[x].son[1] );tree[x].flag 0;}
}bool isroot ( int x ) {return tree[tree[x].f].son[0] x || tree[tree[x].f].son[1] x;
}void rotate ( int x ) { int fa tree[x].f; int Gfa tree[fa].f;int k ( tree[fa].son[1] x );if ( isroot ( fa ) )tree[Gfa].son[tree[Gfa].son[1] fa] x;tree[x].f Gfa; tree[fa].son[k] tree[x].son[k ^ 1];if ( tree[x].son[k ^ 1] )tree[tree[x].son[k ^ 1]].f fa;tree[x].son[k ^ 1] fa;tree[fa].f x;update ( fa );update ( x );
}void splay ( int x ) {int Top 0, y x;st[ Top] y;while ( isroot ( y ) )st[ Top] y tree[y].f;while ( Top )pushdown ( st[Top -- ] );while ( isroot ( x ) ) {int fa tree[x].f, Gfa tree[fa].f;if ( isroot ( fa ) )( ( tree[Gfa].son[0] fa ) ^ ( tree[fa].son[0] x ) ) ? rotate ( x ) : rotate ( fa );rotate ( x );}
}void access ( int x ) {for ( int son 0;x;son x, x tree[x].f ) {splay ( x );tree[x].son[1] son;update ( x );}
}void MakeRoot ( int x ) {access ( x );splay ( x );reverse ( x );
}int FindRoot ( int x ) {access ( x );splay ( x );while ( tree[x].son[0] ) {pushdown ( x );x tree[x].son[0];}splay ( x );return x;
}void split ( int x, int y ) {MakeRoot ( x );access ( y );splay ( y );
}void link ( int x, int y ) {MakeRoot ( x );if ( FindRoot ( y ) x ) return;tree[x].f y;
}void cut ( int x, int y ) {MakeRoot ( x );if ( FindRoot ( y ) ! x || tree[y].f ! x || tree[y].son[0] )return;tree[y].f tree[x].son[1] 0;update ( x );
}int main() {scanf ( %d %d, n, m );for ( int i 1;i n;i )scanf ( %d, tree[i].val );int opt, x, y;for ( int i 1;i m;i ) {scanf ( %d %d %d, opt, x, y );switch ( opt ) {case 0 : {split ( x, y );printf ( %d\n, tree[y].sum );break;}case 1 : link ( x, y ); break;case 2 : cut ( x, y ); break;case 3 : {splay ( x );tree[x].val y;break;}}}return 0;
}code封装版
#include cstdio
#include iostream
using namespace std;
#define maxn 300005
struct Link_Cut_Tree {struct node {int f, val, sum, flag, son[2];}tree[maxn];int st[maxn];void reverse ( int x ) {swap ( tree[x].son[0], tree[x].son[1] );tree[x].flag ^ 1; }void update ( int x ) {tree[x].sum tree[tree[x].son[0]].sum ^ tree[tree[x].son[1]].sum ^ tree[x].val;}void pushdown ( int x ) {if ( tree[x].flag ) {if ( tree[x].son[0] )reverse ( tree[x].son[0] );if ( tree[x].son[1] )reverse ( tree[x].son[1] );tree[x].flag 0;}}bool isroot ( int x ) {return tree[tree[x].f].son[0] x || tree[tree[x].f].son[1] x;}void rotate ( int x ) { int fa tree[x].f; int Gfa tree[fa].f;int k ( tree[fa].son[1] x );if ( isroot ( fa ) )tree[Gfa].son[tree[Gfa].son[1] fa] x;tree[x].f Gfa; tree[fa].son[k] tree[x].son[k ^ 1];if ( tree[x].son[k ^ 1] )tree[tree[x].son[k ^ 1]].f fa;tree[x].son[k ^ 1] fa;tree[fa].f x;update ( fa );update ( x );}void splay ( int x ) {int Top 0, y x;st[ Top] y;while ( isroot ( y ) )st[ Top] y tree[y].f;while ( Top )pushdown ( st[Top -- ] );while ( isroot ( x ) ) {int fa tree[x].f, Gfa tree[fa].f;if ( isroot ( fa ) )( ( tree[Gfa].son[0] fa ) ^ ( tree[fa].son[0] x ) ) ? rotate ( x ) : rotate ( fa );rotate ( x );}}void access ( int x ) {for ( int son 0;x;son x, x tree[x].f ) {splay ( x );tree[x].son[1] son;update ( x ); }}void MakeRoot ( int x ) {access ( x ); splay ( x );reverse ( x );}int FindRoot ( int x ) { access ( x );splay ( x );while ( tree[x].son[0] ) {pushdown ( x );x tree[x].son[0];}splay ( x );return x;}void split ( int x, int y ) {MakeRoot ( x );access ( y ); splay ( y );}void link ( int x, int y ) { MakeRoot ( x );if ( FindRoot ( y ) x ) return;tree[x].f y;}void cut ( int x, int y ) { MakeRoot ( x );if ( FindRoot ( y ) ! x || tree[y].f ! x || tree[y].son[0] )return;tree[y].f tree[x].son[1] 0;update ( x );}}LCT;
int n, m;int main() {scanf ( %d %d, n, m );for ( int i 1;i n;i )scanf ( %d, LCT.tree[i].val );int opt, x, y;for ( int i 1;i m;i ) {scanf ( %d %d %d, opt, x, y );switch ( opt ) {case 0 : {LCT.split ( x, y );printf ( %d\n, LCT.tree[y].sum );break;}case 1 : LCT.link ( x, y ); break;case 2 : LCT.cut ( x, y ); break;case 3 : {LCT.splay ( x );LCT.tree[x].val y;break;}}}return 0;
}如果本蒟蒻乱写的对您有帮助点个赞呗(づ3)づ╭❤
