山西住房城乡建设厅网站,青岛代理记账公司现状,佛山seo培训,游戏开发工程师招聘文章目录前言解析原理rotate(x)splay(x)access(x)findroot(x)makeroot(x)split(x,y)link(x,y)cut(x,y)pushdown(x)完整代码所谓Link Cut Tree#xff0c;就是林可卡特发明的tree #xff08;逃#xff09;
前言
终于走到了这一天… 其实感觉没有预想的那么难#xff08;单…
文章目录前言解析原理rotate(x)splay(x)access(x)findroot(x)makeroot(x)split(x,y)link(x,y)cut(x,y)pushdown(x)完整代码所谓Link Cut Tree就是林可卡特发明的tree 逃
前言
终于走到了这一天… 其实感觉没有预想的那么难单纯就学习算法和理解模板而言 至少感觉比学平衡树轻松
LCT是一种很强大的树形数据结构 最重要的功能优势就是支持单log的复杂度完成加边、删边、换根的操作 在路径问题上十分强大
解析
原理
LCT的核心原理是实链剖分 和重链剖分类似的将一棵树中的边分为实边和虚边 每个结点的最多有一条连向儿子的实边与树链剖分不同的也可以没有
把实边连成的链成为实链 把在同一条实链上的结点放到同一个splay中 这个splay的中序遍历就是这条链从上到下的顺序 这样就间接的表示了所有实边的信息
那么如何表示虚边 假设原树上有一条 fafafa 指向sonsonson的虚边 就把son所在的splay的根节点指向fa从而表示出虚边 根节点也有父亲了如何判断根节点呢 只有该结点的父亲的左右儿子都不是自己那么这个结点就是根节点
inline bool isroot(int x) {return tr[f[x]][0]!xtr[f[x]][1]!x;
}下面我们来讲讲具体的操作函数
rotate(x)
和普通的splay大同小异唯一需要注意的是有一句
if(gfa) tr[gfa][which(fa)]x;变成了
if(!isroot(fa)) tr[gfa][which(fa)]x;较好理解因为判定根的条件变了
splay(x)
将x转到所在splay的根节点由于只需要转到根一个功能穿一个参即可 注意不同于正常的splay需要先把链上的标记下放 实现有两种方法 第一种是递归
void pushall(int x){//printf(%d\n,x);if(!isroot(x)) pushall(f[x]);pushdown(x);
}第二种是手写栈
int yx,top0;zhan[top]y;while(!isroot(y)) zhan[top]yf[y];建议使用第二种因为第一种不小心容易写完函数后忘记调用别问我为什么知道 然后和rotate类似的对根的判断略有区别 不过都是一个道理
inline void splay(int x) {int yx,top0;zhan[top]y;while(!isroot(y)) zhan[top]yf[y];while(top) pushdown(zhan[top--]);for(int fa; faf[x],!isroot(x); rotate(x)) {if(!isroot(fa)) which(fa)which(x)?rotate(fa):rotate(x);}return;
}access(x)
重中之重LCT的灵魂 功能提取出 x 到根节点的一条实链 先把x的尾巴去掉具体来说就是转到根然后砍掉右子树 然后一路往上直至 fa 指针为空过程中需要改变实虚边的状态
inline void access(int x) {for(int y(0); x; yx,xf[x]) {splay(x);tr[x][1]y;pushup(x);if(y) f[y]x;}return;
}findroot(x) 功能找到x所在的树的根节点注意是真实的树而不是splay的根 先access(x)然后把x转到根不断往左走即可
inline int findroot(int x) {access(x);splay(x);while(pushdown(x),tr[x][0]) xtr[x][0];splay(x);return x;
}makeroot(x)
功能把x作为其所在树的根换根 前面说过父子关系在splay中的体现是中序遍历 所以换根即颠倒x-rt路径上所有的父子关系其实就是区间翻转 先access(x)然后转到根然后用类似文艺平衡树的方式在x上打一个翻转标记即可
inline void makeroot(int x) {access(x);splay(x);tag(x);return;
}最愉快的代码
split(x,y) 功能提取出以x、y为两端点的实链前提是二者联通 makeroot(x)之后access(y)即可 为了后面方便常常再加一步splay(y)不然连根是谁都不知道提取个寂寞
inline void split(int x,int y){//y is fathermakeroot(x);access(y);splay(y);return;
}link(x,y) 功能加一条边(x,y)(x,y)(x,y)在有出现环的时候忽略操作 出现环即xy原来就联通可以用findroot判掉 否则先makeroot(x)然后把f(x)指向y即可 记得按需要更新y的信息
inline void link(int x,int y) {makeroot(x);if(findroot(y)x) return;f[x]y;pushup(y);//printf(link: %d - %d\n,x,y);
}cut(x,y) 功能切断边(x,y)(x,y)(x,y)在没有这条边时忽略操作 先makeroot(x)然后access(y)splay(y)到根 此时如果存在这条边必然x和y是在同一个splay中 判断的充要条件x是y的左儿子且x没有右儿子比较显然 如果存在的话把这条y的左儿子和x的父亲赋值为0即可 不要忘记更新y的信息又一次
inline void cut(int x,int y) {makeroot(x);access(y);splay(y);if(tr[y][0]!x||tr[x][1]) return;tr[y][0]f[x]0;pushup(y);return;
}pushdown(x)
大部分时候只需要翻转 一个看到的地方都说比较“稳妥”的写法 谁不喜欢稳妥呢
inline void tag(int x) {if(x) {rev[x]^1;swap(tr[x][0],tr[x][1]);}
}
inline void pushdown(int x) {if(rev[x]){rev[x]0;tag(tr[x][0]);tag(tr[x][1]);}return;
}完整代码
经验传送门
#includebits/stdc.h
using namespace std;
#define ll long long
const int N2e5100;
const int mod1e97;
const double eps1e-9;
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m;#define ls(o) tr[o][0]
#define rs(o) tr[o][1]
int tr[N][2],f[N],rev[N],val[N],mx[N];
inline bool isroot(int x) {return tr[f[x]][0]!xtr[f[x]][1]!x;
}
inline bool which(int x) {return tr[f[x]][1]x;
}
inline void pushup(int x) {if(x){mx[x]x;if(ls(x)val[mx[ls(x)]]val[mx[x]]) mx[x]mx[ls(x)];if(rs(x)val[mx[rs(x)]]val[mx[x]]) mx[x]mx[rs(x)];}return;
}
inline void tag(int x) {if(x) {rev[x]^1;swap(tr[x][0],tr[x][1]);}
}
inline void pushdown(int x) {if(rev[x]){rev[x]0;tag(tr[x][0]);tag(tr[x][1]);}return;
}
void debug(int x) {if(!x) return;pushdown(x);debug(tr[x][0]);printf(debug: x%d ls%d rs%d\n,x,tr[x][0],tr[x][1]);debug(tr[x][1]);return;
}
inline void rotate(int x) {int faf[x],gfaf[fa];int dwhich(x),sontr[x][d^1];f[x]gfa;if(!isroot(fa)) tr[gfa][which(fa)]x;f[fa]x;tr[x][d^1]fa;if(son){f[son]fa;}tr[fa][d]son;pushup(fa);pushup(x);return;
}
int zhan[N];
inline void splay(int x) {int yx,top0;zhan[top]y;while(!isroot(y)) zhan[top]yf[y];while(top) pushdown(zhan[top--]);for(int fa; faf[x],!isroot(x); rotate(x)) {if(!isroot(fa)) which(fa)which(x)?rotate(fa):rotate(x);}return;
}
inline void access(int x) {for(int y(0); x; yx,xf[x]) {splay(x);tr[x][1]y;pushup(x);if(y) f[y]x;}return;
}
inline void makeroot(int x) {access(x);splay(x);tag(x);return;
}
inline int findroot(int x) {access(x);splay(x);while(pushdown(x),tr[x][0]) xtr[x][0];splay(x);return x;
}
inline void link(int x,int y) {makeroot(x);if(findroot(y)x) return;f[x]y;pushup(y);//printf(link: %d - %d\n,x,y);
}
inline void cut(int x,int y) {makeroot(x);access(y);splay(y);if(tr[y][0]!x||tr[x][1]) return;tr[y][0]f[x]0;pushup(y);return;
}
inline void split(int x,int y){//y is fathermakeroot(x);access(y);splay(y);return;
}
