Splay 核心代码。
总结就是双旋
void rot(int x,int &k){
int y=tr[x].fa,z=tr[y].fa;
int kd=(tr[y].son[0]==x)?0:1;
if(y==k) k=x;
else {
if(tr[z].son[0]==y) tr[z].son[0]=x;
else tr[z].son[1]=x;
}
tr[y].son[kd]=tr[x].son[!kd]; tr[tr[y].son[kd]].fa=y;
tr[x].son[kd^1]=y; tr[y].fa=x; tr[x].fa=z;
pushup(y); pushup(x);
}
void splay(int x,int &k){
while(x!=k){
int y=tr[x].fa,z=tr[y].fa;
if(y!=k){
if((tr[y].son[0]==x) ^ (tr[z].son[0]==y)) rot(x,k);
else rot(y,k);
}
rot(x,k);
}
}
LCT
对于一棵树中，每个节点选中一个儿子的边为实边，其他为虚边，这样就构成了若干个实链，每个 \(Splay\) 维护一条实链。基于这样的实链剖分， \(LCT\) 应运而生。 \(LCT\) 维护的对象其实是一个森林。
支持的操作如下：
- 查询、修改链上的信息（最值，总和等）
- 换根
- 动态连边、删边
- 动态维护连通性
- 查询、修改子树信息（？）
\(LCT\) 的主要性质：
- 每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。
- 每个节点包含且仅包含在一个 \(\rm Splay\) 中。
- 边分为实边贺虚边，实边包含在 \(Splay\) 中，虚边由一棵 \(\rm Splay\) 指向另外一个节点（该 \(\rm Splay\) 中中序遍历最靠前的点在原树中的父亲）。
\(\rm Access(x)\)
定义打通该节点到根节点的实链。构造出一个 \(\rm Splay\) 表示根到指定点的实链 。
将指定点 \(\rm Splay\) 到根节点。直接将虚边变成实边。
若原来的虚边指向父亲为 \(fp\) ，则直接根据中序遍历，将 \(fp\) 的右儿子指向 \(x\) 。然后继续向上重复操作，一直到根节点。
Iv access(int x){
for(int y=0;x;y=x,x=tr[x].fa)
splay(x) , tr[x].c[1]=y, pushup(x);
}
\(\rm evert\)
换根。 打通指定点到根的实链然后原本是中序遍历最后一个节点，变成第一个节点，交换左右儿子即可。
需要下传交换标记，后文会提到。
Iv revr(int u){ swap(tr[x].c[0],tr[x].c[1]); tr[x].rev^=1;}
Iv pushdn(int p) {
if(tr[p].rev){
if(tr[p].c[0]) revr[tr[p].c[0]];
if(tr[p].c[1]) revr[tr[p].c[1]];
tr[p].rev=0;
}
}
inline void evert(int x){
access(x); splay(x); revr(x);
}
\(\rm splay\)
因为有了下传标记的操作，所以 \(\rm splay\) 部分有所更改。
注意标记要从上到下下传。
Iv pdnw(int p){
if(!isroot(p)) pdnw(tr[p].fa);
pushdn(p);
}
Iv rotate(int p){
int fp=tr[p].fa,gp=tr[fp].fa;
int d=gd(p);
if(isroot(fp)) tr[p].fa=tr[fp].fa;
else cnet(gp,gd(fp),p);
cnet(fp,d,tr[p].c[!d]); cnet(p,!d,fp);
pushup(fp); pushup(p);
}
Iv splay(int p){
pdnw(p);
while(!isroot(p)){
int fp=tr[p].fa;
if(!isroot(fp)){
if(gd(fp)==gd(p)) rot(fp);
else rot(p);
}
rot(p);
}
}
\(\rm findrt\)
找到根节点。 先将 \(x\) \(\rm splay\) 到根，根据中序遍历和二叉搜索树的性质查找。
记得 \(\rm pushdown\)。
inline int findrt(int u){
access(u); splay(u); pushdn(u);
while(tr[u].c[0]) u=tr[u].c[0],pushdn(u);
splay(u);
return u;
}
#### $\rm link$
连接一条边。
```cpp
Iv link(int u,int v){
evert(u); if(findrt(v)!=u) tr[u].fa=v;
}
*/
\(\rm cut\)
断开一条边。
Iv cut(int u,int v){
evert(v); access(u); splay(u);
if(tr[v].c[1] || tr[u].c[0]!=v) return ;
cutd(u,0); pushup(u);
}
\(\rm splitl\)
将 \(u\to v\) 这条链放到一个 \(\rm Splay\) 里面，且让 \(u\) 的中序遍历比 \(v\) 小。
并将 \(v\) \(\rm splay\) 使得 \(v\) 的左儿子为 \(u\)。
不过我还是喜欢将这个函数拆出来写（。 可以用来查询信息？？？
Iv splitl(int u,int v){
evert(u); access(v); splay(v);
}
完整代码：
namespace LCT{
#define ls tr[p].c[0]
#define rs tr[p].c[1]
struct node{
int c[2],fa;
int rev;
node(){c[0]=c[1]=fa=0;rev=0;}
} tr[N+5];
inline bool gd(int p) { return tr[tr[p].fa].c[1]==p;}
inline bool isroot(int p) { return !tr[p].fa || tr[tr[p].fa].c[gd(p)]!=p;}
Iv cnet(int u,int d,int v){if(u) tr[u].c[d]=v; if(v) tr[v].fa=u;}
Iv cutd(int u,int d){ tr[ tr[u].c[d] ].fa=0 ; tr[u].c[d]=0;}
Iv revr(int u){ swap(tr[u].c[0],tr[u].c[1]); tr[u].rev^=1;}
Iv pushdn(int p) {
if(tr[p].rev){
if(tr[p].c[0]) revr(tr[p].c[0]);
if(tr[p].c[1]) revr(tr[p].c[1]);
tr[p].rev=0;
}
//以及其他需要维护的信息
}
Iv pushup(int p) { ;}
Iv pdnw(int p){
if(!isroot(p)) pdnw(tr[p].fa);
pushdn(p);
}
Iv rot(int p){
int fp=tr[p].fa,gp=tr[fp].fa;
int d=gd(p);
if(isroot(fp)) tr[p].fa=tr[fp].fa;
else cnet(gp,gd(fp),p);
cnet(fp,d,tr[p].c[!d]); cnet(p,!d,fp);
pushup(fp); pushup(p);
}
Iv splay(int p){
pdnw(p);
while(!isroot(p)){
int fp=tr[p].fa;
if(!isroot(fp)){
if(gd(fp)==gd(p)) rot(fp);
else rot(p);
}
rot(p);
}
}
Iv access(int x){
for(int y=0;x;x=tr[y=x].fa)
splay(x) , tr[x].c[1]=y, pushup(x);
}
Iv evert(int x){
access(x); splay(x); revr(x);
}
inline int findrt(int u){
access(u); splay(u);
while(tr[u].c[0]) pushdn(u),u=tr[u].c[0];
splay(u);
return u;
}
Iv splitl(int u,int v){
evert(u); access(v); splay(v);
}
Iv link(int u,int v){
evert(u); if(findrt(v)==u) return ;
splay(v); tr[u].fa=v;
}
Iv cut(int u,int v){
evert(v); access(u); splay(u);
if(tr[v].c[1] || tr[u].c[0]!=v) return ;
cutd(u,0); pushup(u);
}
#undef ls
#undef rs
}
using namespace LCT;
一些 LCT 的套路。
-
有些题可以把操作从后往前做，就可以把题目中的删边转化成加边。
-
边权转点权。 如有边 \(u\stackrel{E_i}{\longrightarrow}v\)，点 \(u\) 和 点 \(v\) 由边 \(E_i\) 相连。 我们可以开一个新的点 \(x\) 表示边 \(E_i\) 。将边权信息存到点权上。 连接 \(u-x,v-x\)。维护生成树。
-
维护子树信息 ，分为实子树和虚子树的贡献。实子树好维护，虚子树需要在改变虚实边时处理，即 \(\rm link\) 和 \(\rm assert\) 的时候特殊处理。
-
最小深度，树的直径，先鸽了。
应用：
维护生成树
删边转加边，维护最小生成树。
将边从大到小加边，然后动态维护最小生成树。本质是枚举边的最小值，通过维护最小生成树使得最大值最大。
维护联通性&双联通分量
并查集只能撤销不能删除。用 LCT 完成删边加边操作，findrt 查询连通性。
首先离线，删边转加边。要求关键路径，本质是要求我们把边双缩成一点后再查询两点距离。可以利用 LCT 来维护这个操作
每次把一条链变成一个环时，可以直接暴力地把这个链拆开，用并查集把链上每一个点连到新的代表这个环的点。就做完了。注意 \(access\) 找父亲时要查找并查集的父亲
int geph(int x){
if(Fa[x]==x) return x;
else return Fa[x]=geph(Fa[x]);
}
Iv access(int x){
for(int y=0;x;y=x,x=tr[y].fa=geph(tr[y].fa))
splay(x) , tr[x].c[1]=y, pushup(x);
}
void del(int p,int fu){
Fa[p]=fu;
if(tr[p].c[0]) del(tr[p].c[0],fu);
if(tr[p].c[1]) del(tr[p].c[1],fu);
}
Iv link(int u,int v){
if(u==v) return ;
evert(u); if(findrt(v)!=u) {tr[u].fa=v; return ;}
del(tr[u].c[1],u); tr[u].c[1]=0; pushup(u);
}
维护树上深度&直径
做法一：动态维护树的深度。理论上也支持删边操作，复杂度 \(O(n\log^2 n)\)。
对于查询，我们将查询点 \(\rm makeroot\) 只要能查询这个点的最大深度即可。
我们用一个 \(multiset\) 将轻节点的信息存起来。因为 splay时所代表的链传递上去的信息不变，所以在 \(access\) 的时候修改即可。
我们记录两个值 \(mxd,mxz\) 。记录的是 \(splay\) 表示的链中，这个节点的子树（不包含链中深度比他小的节点）的最大深度，因为翻转的时候树的深度会颠反，所以同时记录反转后的深度交换即可。
根据左右子树顺序传递信息。
tr[p].mxd=max(tr[ls].mxd,max(*(--tr[p].sdp.end()),tr[rs].mxd)+tr[ls].siz+1);
tr[p].mxz=max(tr[rs].mxz,max(*(--tr[p].sdp.end()),tr[ls].mxz)+1+tr[rs].siz);
做法二：动态维护树的直径。
关于直径的性质：
- 两棵树合并后，新的直径的两个端点一定来源于原来两条直径中的四个端点。
- 一个点距离最远的点一定是直径两个端点之一。
那么我们将直径信息存在并查集的根节点，合并时利用 \(\rm LCT\) 求距离来算出新的直径。 复杂度 \(O(n\log n)\)
查询子树信息
查询本质是求两颗子树大小的乘积。维护子树的大小，查询的时候直接单独拉出来这条边即可。
将实子树大小和虚子树大小分开处理。 虚子树大小在 \(assert\) 的时候维护一下。
看代码理解吧。
Iv pushup(int p) { tr[p].sz=tr[lc].sz+tr[rc].sz+tr[p].szx+1; }
Iv access(int x){
for(int y=0;x;x=tr[y=x].fa){
splay(x); tr[x].szx+=tr[tr[x].c[1]].sz-tr[y].sz;
tr[x].c[1]=y; pushup(x);
}
}
Iv link(int u,int v){
evert(u); evert(v);
tr[u].fa=v;tr[v].szx+=tr[u].sz; pushup(v);
}
服了，调了一天，维护信息跟虚边有关的一定要将 \(u\) 和 \(v\) 都转到跟，否则，信息会无法更新 。
不难发现，题目求的就是各个树的重心。
重心性质：
- 把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
- 当树的大小为奇数是，重心是唯一的，否则，重心有两个且由一条边连接。
- 重心的所有子树大小均不大于树的大小 \(S/2\)。互为充要条件，可以证明。
根据这些性质，我们将重心存到并查集的根，每次合并两棵树，把两个重心的路径拿出来，寻找新的重心，在 Splay 树上二分。
具体的，如果一个点不为重心，那么重心只会存在于左儿子和右儿子的一个方向。根据重心性质，我们递归儿子重量更大的一边。根据重心性质可以证明。 复杂度 \(O(n\log n)\)。
inline int findzx(int p){
int lsm=0,rsm=0,S=tr[p].sz,np=N+5;
while(p){
pushdn(p);
int lm=tr[ls].sz+lsm,rm=tr[rs].sz+rsm;
if(lsm>S/2 || rsm>S/2) break;
if(lm<=S/2 && rm<=S/2){
if(S & 1) { np=p; break;}
else {
if(np>p) np=p;
else break;
}
}
if(lm<rm) lsm+=tr[ls].sz+tr[p].szx+1 , p=rs;
else rsm+=tr[rs].sz+tr[p].szx+1, p=ls;
}
splay(np);
return np;
}
还有一种更为朴素的做法，启发式合并。重心性质
添加或者删除一个点，重心只一个一次，因此，暴力地加点判断重心大概可以做，可能会比较复杂。 \(O(n\log^2n)\)。
SAM + LCT 合成品。动态维护后缀链接，查询子树大小。