Link-Cut-Tree(1)

参考论文

求解范围:(动态树问题)

  • 树上路径查询、修改
  • 动态连边、删边
  • 换根
  • lca

算法逻辑

概念:

  • 类似树链剖分,把一棵树拆成许多链,每个链用splay维护(链上的为实边,否则为虚边),splay中以\(dep\)为关键字(左浅右深),splay里点之间用\(fa\)和\(son[0/1]\)连接,不同链之间用\(par\)连接(par是单向的(下->上))。
    \(par\)存在splay的根中,值为该splay中 \(dep\) 最小(浅)的父亲(可以想象一下跳到原树中的那条链的顶端的父亲)

流程:

access

  • 作用:将u往上到根的路径,拆成一条链
  • 操作:
    1.\(v\)为过程中一点,且到右儿子存在实边,则需要断开\(v\)与右端点的实边(变为虚边)。
    2.\(u\)沿着par往上跳(直到根),每次到一个新的splay就跟上一个splay链合并一下。(同时更新1)
  • Code:
void access(int x) {
	int y=0;
	while(x) {
		splay(x);P_dw(x);
		if(son[x][1]) fa[son[x][1]]=0,par[son[x][1]]=x;
		son[x][1]=y;fa[y]=x;	//??splay
		P_up(x);
		y=x;x=par[x];
	}
}

LCA(x,y)

  • 操作:\(access(x)\),\(access(y)\)中\(y\)往上跳到与根在同一个splay里面时,所在的点\(d\)即为lca。
  • 证明:显然\(par\)的定义是到该splay树最浅的点的fa,然而\(d\)往下到\(y\)的第一条边为虚边,而且根据定义刚好跳到\(d\)。

小细节

  • \(par\)是需要存储于每个splay_tree的根处,所以每次splay后要手动更新赋值。
  • splay()前要手动递归从根到该点Pushdown。
  • 可以不用\(par\),只用\(fa\),不过要慢一些呀。

ps.还有很多其余的操作可以见下面这道题的代码:
OTOCI

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e6+5;
    bool Lazy[N];
    int val[N],son[N][2],sum[N];
    int par[N],fa[N];
    int q,n;
    void P_up(int x) {sum[x]=val[x]+sum[son[x][0]]+sum[son[x][1]];}
    void P_dw(int x) {
    	if(!Lazy[x])return;
    	swap(son[x][0],son[x][1]);
    	Lazy[son[x][0]]^=1,Lazy[son[x][1]]^=1;Lazy[x]=0;
    }
    bool Type(int x) {return son[fa[x]][1]==x;}
    void rotate(int x) {
    	int y=fa[x],z=fa[y],k=Type(x);
    	fa[x]=z;if(z)son[z][Type(y)]=x;
    	son[y][k]=son[x][k^1];fa[son[y][k]]=y;
    	son[x][k^1]=y;fa[y]=x;
    	P_up(y);P_up(x);
    }
    void _spdw(int u,int x) {
    	if(!fa[u]) {par[x]=par[u];P_dw(u);return;}
    	_spdw(fa[u],x);
    	P_dw(u);
    }
    void splay(int x) {
    	_spdw(x,x);
    	for(int f=fa[x];f=fa[x];rotate(x)) {
    		if(fa[f]) rotate(Type(x)==Type(f)?f:x);
    	}
    }
    void access(int x) {
    	int y=0;
    	while(x) {
    		splay(x);P_dw(x);
    		if(son[x][1]) fa[son[x][1]]=0,par[son[x][1]]=x;
    		son[x][1]=y;fa[y]=x;	//??splay
    		P_up(x);
    		y=x;x=par[x];
    	}
    }
    void mk_rt(int x) {access(x);splay(x);Lazy[son[x][0]]^=1;Lazy[son[x][1]]^=1;swap(son[x][0],son[x][1]);}
    int Fd_rt(int x) {access(x);splay(x);while(son[x][0])x=son[x][0];splay(x);return x;}
    void split(int x,int y)	{mk_rt(x);access(y);splay(y);}	//??
    void Link(int x,int y) {mk_rt(x);par[x]=y;}
    int Sum(int x,int y) {split(x,y);return sum[y];}
    int main() {
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",&val[i]),sum[i]=val[i];
    	scanf("%d",&q);
    	while(q--) {
    		char ch[21]; int x,y;
    		scanf("%s%d%d",ch,&x,&y);
    		if(ch[0]=='b') {
    //			printf("!%d %d\n",Fd_rt(x),Fd_rt(y));
    			if(Fd_rt(x)!=Fd_rt(y)) {printf("yes\n");Link(x,y);}
    			else printf("no\n");
    		}
    		else if(ch[0]=='p') {
    			splay(x);val[x]=y;P_up(x);
    		}
    		else {
    //			printf("!%d %d\n",Fd_rt(x),Fd_rt(y));
    			if(Fd_rt(x)!=Fd_rt(y)) {printf("impossible\n");continue;}
    			printf("%d\n",Sum(x,y));
    		}
    	}
    	return 0;
    }
上一篇:[IOI2021]distribute candies


下一篇:FPGA之VGA转HDMI之并行串行转换模块编写