首页 > 代码库 > 动态树之link-cut tree
动态树之link-cut tree
说好的专题。。。
lct的一些概念看论文 杨哲《QTREE解法的一些研究》 简单易懂。
首先不要把lct想象得很难，其实很水的。lct就是很多splay树维护的树。。。
lct的access操作就是在原树中拓展一条点到根的类二叉树出来（用splay来维护）
这里，splay树是按深度作为关键字的，当然，在无向图中（无环）可以任意指定一个点为根，这点要切记（因为在这里操作时，有些操作需要换根，所以一定要理解）
link操作就是将点作为这颗类二叉树的根，然后合并
cut操作就是将点作为这颗二叉树的根，然后在拓展一条另一个点的splay路径（此时这两个点一定要有边连接，这样使得拓展上来的根一定在另一个点拓展上来的splay树的左子树上，因为他们有边连接），将左子树的父亲设为0，并且去掉左子树
getroot操作就是将点拓展了splay后，并且将它伸展到根，此时，最小的子树（深度最浅，即最左的子树）就是这颗splay的根
makeroot操作就是将点拓展为现在所在的树的根，即换根，伸展到根后只需要将左右子树反向，就是将深度换了（根据splay有良好的下放操作，我们将翻转用标记来翻转，使得时间复杂度减小）
额，我自己都觉得说得不好 。。囧
说些注意的地方吧：
- 在维护splay树时，当x为这棵树的根时，并不意味着它没有父亲，只是他的父亲没有这个孩子（这点一定要理解！！），因为我们维护的是一棵多叉树，但是我们拓展的是二叉树，所以，你懂的。怎么修改呢，在原来splay操作的判null的地方都用现在的特判。
- 在旋转时，还需要判断父亲的父亲是否为上边所说的那样，如果是，就不要更新他，因为这两个点不在一颗splay上。
- splay操作时，下放标记我们要用一个栈到达他的根往下放标记。
- 不要把splay和原树搞混。
- 不要认为只有一颗splay树。
- 不要认为理所当然，，，在思考的时候好好思考。
好了，我认为差不多了。。
一些题我之前也发了博文，我现在再放出来。。
【BZOJ】2002: [Hnoi2010]Bounce 弹飞绵羊
#include <cstdio>#define read(x) x=getint()using namespace std;inline int getint() { char c; int ret=0; for(c=getchar(); c<‘0‘ || c>‘9‘; c=getchar()); for(; c>=‘0‘ && c<=‘9‘; c=getchar()) ret=ret*10+c-‘0‘; return ret; }const int N=200005;struct node* null;struct node { node *f, *ch[2]; int s; void pushup() { s=1+ch[0]->s+ch[1]->s; } bool d() { return f->ch[1]==this; } void setc(node* c, bool d) { ch[d]=c; c->f=this; } bool check() { return f==null || (f->ch[0]!=this && f->ch[1]!=this); } //check操作是lct特地的，因为为了省空间，我们不开n颗splay，只用节点关联就行了，这样就无法避免父亲没有这个孩子的情况。所以还要特判}*nd[N];void rot(node* r) { node* f=r->f; bool d=r->d(); if(f->check()) r->f=f->f; else f->f->setc(r, f->d()); //这里一定要这样写，不然会让null的孩子改变，这样在splay的循环就会死循环T_T f->setc(r->ch[!d], d); r->setc(f, !d); f->pushup();}inline void splay(node* r) { while(!r->check()) if(r->f->check()) rot(r); else r->d()==r->f->d()?(rot(r->f), rot(r)):(rot(r), rot(r)); r->pushup();}inline void access(node* f) { for(node* c=null; f!=null; f=f->f) { splay(f); f->setc(c, 1); f->pushup(); c=f; }}inline void link(node* c, node* f) { access(c); splay(c); c->ch[0]->f=null; c->ch[0]=null; c->f=f; c->pushup();}inline void init() { null=new node; null->s=0; null->f=null->ch[0]=null->ch[1]=null;}int main() { init(); int n, t; read(n); for(int i=0; i<n; ++i) { nd[i]=new node; nd[i]->s=1; nd[i]->ch[0]=nd[i]->ch[1]=nd[i]->f=null; } for(int i=0; i<n; ++i) { read(t); if(i+t<n) nd[i]->f=nd[i+t]; } int m, a, b, c; read(m); for(int i=0; i<m; ++i) { read(a); read(b); if(a==1) { access(nd[b]); splay(nd[b]); printf("%d\n", nd[b]->s); } else { read(c); if(b+c<n) link(nd[b], nd[b+c]); else link(nd[b], null); } } return 0;}
【BZOJ】1036: [ZJOI2008]树的统计Count
#include <cstdio>#include <iostream>using namespace std;#define dbg(x) cout << #x << "=" << x << endl#define read(x) x=getint()#define print(x) printf("%d", x)#define max(a,b) ((a)>(b)?(a):(b))const int oo=~0u>>1;inline int getint() { char c; int ret=0, k=1; for(c=getchar(); c<‘0‘ || c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) ret=ret*10+c-‘0‘; return k*ret; }const int N=30010, M=100005;int ihead[N], inext[M], to[M], cnt, q[N], front, tail, n, m;bool vis[N];struct node* null;struct node { node* fa, *ch[2]; int w, sum, mx; bool d() { return fa->ch[1]==this; } bool check() { return fa->ch[0]!=this && fa->ch[1]!=this; } void setc(node* c, bool d) { ch[d]=c; c->fa=this; } void pushup() { sum=w+ch[0]->sum+ch[1]->sum; mx=max(w, max(ch[0]->mx, ch[1]->mx)); }}*nd[N];inline void rot(node* r) { node* fa=r->fa; bool d=r->d(); if(fa->check()) r->fa=fa->fa; else fa->fa->setc(r, fa->d()); fa->setc(r->ch[!d], d); r->setc(fa, !d); fa->pushup();}inline void splay(node* r) { while(!r->check()) if(r->fa->check()) rot(r); else r->d()==r->fa->d()?(rot(r->fa), rot(r)):(rot(r), rot(r)); r->pushup();}inline node* access(node* fa) { node* c=null; for(; fa!=null; c=fa, fa=fa->fa) { splay(fa); fa->setc(c, 1); fa->pushup(); } return c;}inline void bfs() { vis[1]=1; int u, v, i; front=tail=0; q[tail++]=1; while(front!=tail) { u=q[front++]; for(i=ihead[u]; i; i=inext[i]) if(!vis[v=to[i]]) { vis[v]=1; nd[v]->fa=nd[u]; q[tail++]=v; } }}inline void add(const int &u, const int &v) { inext[++cnt]=ihead[u]; ihead[u]=cnt; to[cnt]=v; inext[++cnt]=ihead[v]; ihead[v]=cnt; to[cnt]=u;}int main() { null=new node; null->fa=null->ch[0]=null->ch[1]=null; null->w=null->sum=0; null->mx=oo+1; read(n); int u, v, t; for(int i=1; i<n; ++i) { read(u); read(v); add(u, v); } int w; for(int i=1; i<=n; ++i) { nd[i]=new node; read(w); nd[i]->w=w; nd[i]->ch[0]=nd[i]->ch[1]=nd[i]->fa=null; } bfs(); char c[10]; node* lca=null; read(m); int ans; for(int i=0; i<m; ++i) { scanf("%s", c); if(c[0]==‘C‘) { read(u); read(t); splay(nd[u]); nd[u]->w=t; nd[u]->pushup(); } else if(c[0]==‘Q‘) { read(u); read(v); access(nd[u]); lca=access(nd[v]); splay(nd[u]); if(nd[u]==lca) { if(c[1]==‘M‘) ans=max(lca->w, lca->ch[1]->mx); else ans=lca->w + lca->ch[1]->sum; } else { if(c[1]==‘M‘) ans=max(max(lca->w, nd[u]->mx), lca->ch[1]->mx); else ans=lca->w + lca->ch[1]->sum + nd[u]->sum; } printf("%d\n", ans); } } return 0;}
【BZOJ】2049: [Sdoi2008]Cave 洞穴勘测
#include <cstdio>#include <cstring>#include <string>#include <iostream>#include <cmath>#include <algorithm>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define read(a) a=getnum()#define print(a) printf("%d", a)#define dbg(x) cout << #x << "=" << x << endl;#define dbgarr(a, n) for1(i, 0, n) cout << a[i] << " "; cout << endlinline int getnum() { int ret=0, k=1; char c; for(c=getchar(); c<‘0‘ || c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘ && c<=‘9‘; c=getchar()) ret=ret*10+c-‘0‘; return ret*k; }const int N=10005;int n, m;struct node* null;struct node { node* ch[2], *fa; bool rev; bool d() const { return fa->ch[1]==this; } void setc(node* c, bool d) { ch[d]=c; c->fa=this; } bool check() const { return fa->ch[0]!=this && fa->ch[1]!=this; } void pushdown() { if(rev) { ch[0]->rev^=true; ch[1]->rev^=true; swap(ch[0], ch[1]); rev=false; } }}*nd[N];inline void rot(node* r) { node* fa=r->fa; bool d=r->d(); fa->pushdown(); r->pushdown(); if(fa->check()) r->fa=fa->fa; else fa->fa->setc(r, fa->d()); fa->setc(r->ch[!d], d); r->setc(fa, !d);}void fix(node* x) { if(!x->check()) fix(x->fa); x->pushdown();}inline void splay(node* r) { fix(r); while(!r->check()) if(r->fa->check()) rot(r); else r->d()==r->fa->d()?(rot(r->fa), rot(r)):(rot(r), rot(r));}inline node* access(node* x) { node* y=null; for(; x!=null; y=x, x=x->fa) { splay(x); x->ch[1]=y; } return y;}inline void mkroot(node* x) { access(x)->rev^=true; splay(x);}inline void link(node* x, node* y) { mkroot(x); x->fa=y;}inline void cut(node* x, node* y) { mkroot(x); access(y); splay(y); y->ch[0]->fa=null; y->ch[0]=null;}inline node* findrt(node* x) { access(x); splay(x); while(x->ch[0]!=null) x=x->ch[0]; return x;}int main() { read(n); read(m); null=new node; null->fa=null->ch[0]=null->ch[1]=null; null->rev=false; char s[10]; int u, v; for1(i, 1, n) { nd[i]=new node; nd[i]->fa=nd[i]->ch[0]=nd[i]->ch[1]=null; nd[i]->rev=false; } rep(i, m) { scanf("%s", s); read(u); read(v); if(s[0]==‘Q‘) findrt(nd[u])==findrt(nd[v])?(printf("Yes\n")):(printf("No\n")); else if(s[0]==‘C‘) link(nd[u], nd[v]); else cut(nd[u], nd[v]); } return 0;}
欢迎大家指正～！！！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。