网上的lct一抓一大把,所以我也不再写什么讲解了,只写一写自己的看法.

Link-cut-tree 是用于维护动态树的一种数据结构

所谓动态树就是一片存在边的添加与删除的森林中的一棵树

所以我们要快速处理加边和删边

关于具体的Preferred Child和Preferred Path还有Preferred Edge什么的...就不多说了

不过关于link-cut-tree还有比较重要,刚开始易混淆的地方:

• LCT实际上维护的是两棵树,一棵是原树,另一棵是辅助树.其中原树就是我们要维护的树,而辅助树则是我们根据Preferred Path而维护的Splay森林.即每条Preferred Path都是一棵Splay.
• 所以我们有:
• • 原树与辅助树的结构并不相同
• • 辅助树的根节点不等于原树的根节点
• • 辅助树中的father不等于原树中的father

对LCT的上述性质比较了解后,这里来介绍一下LCT的基本操作.

---

基本操作

Access(u) :

• 将原树上u到根的路径全部变为Prefered Edge,也就是操作之后将会出现一条同时包括原树的根与原树上节点u的Prefferd Path.
• 将在原树上到根所经过的所有辅助树的节点取出,构成一棵新的Splay.也就是说,这时原树中的根与原树着的u共处于同一棵辅助树中.

inline Node* Access(Node *u){    for(Node *v=null;u != null;v=u,u=u->fa)        splay(u),u->ch[1] = v,u->update();    return u;}

findRoot(u) :

• 找到原树中u所在树的根节点(不要忘了我们维护的是一片森林)
• 我们知道根节点的深度一定最小,所以我们Access(u)后,u一定与原树中的根节点同处于一棵Splay(辅助树)中.所以我们知道根节点一定是u所在splay的最左节点.所以我们splay(u)然后找到最靠左的节点即可.
• 注意 : 为了保证均摊复杂度为\(O(logn)\)这里仍需要对找到的根rt进行Splay

inline Node* getRt(Node *u){    Access(u);splay(u);    while(u->ch[0] != null) u = u->ch[0];    splay(u);return u;}

makrRoot(u) :

• 将原树中的u作为原树的根节点,
• 由于原树与辅助树的树形结构并不相同,这里不能直接Access(u),splay(u)就完事.由于splay中是按照deep为关键字排序的,所以在辅助树中无论以那个节点为根,都不会改变原树中的根,因为Splay过程中节点的相对位置不会进行变化,而根的dep最小,一定时时刻刻处于最左端.所以我们可以在Access(u),splay(u)后对u打上翻转标记,表示让u所在的辅助树的根节点进行反转.

我们来分析一下上述操作的正确性:

首先我们知道:

• 所有深度大于u的节点一定都不会被存放在这棵辅助树中

所以我们就发现: Splay(u)后一定不存在任何一个节点在u的右侧

所以现在我们只考虑u左面接上了一条链的情况.(其他情况一定可以转化成链)

这时候我们发现如果我们选择以u作为根,那么这条链上节点的深度关系会中心对称地变化

所以我们在这条链上打上翻转标记即可.

inline void makeRt(Node *u){    Access(u);splay(u);u->tag ^= 1;}

link(u,v) :

• 将u接到v的下面
• 实现这个操作有两一种方法:
• • 方法一: makeroot(u),u->fa = v;
• • 方法二: Access(u),splay(u),u->fa = v;
• 不要管第二种方法了,明显是不对的... ...

这个操作的问题应该不大...

inline void link(Node *u,Node *v){    makeRt(u);u->fa = v;}

cut(u,v)

• 删除u与v之间的边.
• makeRoot(u),Access(v),splay(v),v->ch[0] = v->ch[0]->fa = 0;

inline void cut(Node *u,Node *v){    makeRt(u);Access(v);splay(v);    v->ch[0] = v->ch[0]->fa = null;    v->update();}

如果是删除u与其father的连边呢?

• Access(u),splay(u),u->ch[0] = u->ch[0]->fa = 0;

---

其他操作

get(u,v):

• 取出原树上u->v这一条链并恰好将其存于一棵辅助树中,并返回这棵辅助树的根节点.
• makrRoot(u),Access(v),splay(v) 此时v即为所求

inline Node* get(Node *u,Node *v){    makeRt(u);Access(v);splay(v);    return v;}

lca(rt,u,v):

• 求出以rt为根时的u和v的lca(最近公共祖先)
• makeroot(rt),Access(u),Access(v),此时Access(v)范围值即为所求

inline Node* lca(Node *rt,Node *u,Node *v){    makeRt(rt);Access(u);return Access(v);}

更多操作等会会了再写上来

模板:

hdu 4010 Link-Cut-Tree

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;inline void read(int &x){    x=0;char ch;bool flag = false;    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}const int maxn = 600010;struct Node{    Node *ch[2],*fa;    int w,mx,lazy,tag;    void update();}*null,*it,mem[maxn];void Node::update(){    mx = max(max(ch[0]->mx,ch[1]->mx),w);}inline void init(){    it = mem;null = it++;    null->ch[0] = null->ch[1] = null->fa = null;    null->w = null->mx = null->lazy = null->tag = 0;}inline void newNode(int val){    Node *p = it++;p->w = p->mx = val;    p->ch[0] = p->ch[1] = p->fa = null;    p->lazy = p->tag = 0;}inline void push_down(Node *p){    if(p == null) return;    if(p->lazy != 0){        if(p->ch[0] != null){            p->ch[0]->w += p->lazy;            p->ch[0]->mx += p->lazy;            p->ch[0]->lazy += p->lazy;        }        if(p->ch[1] != null){            p->ch[1]->w += p->lazy;            p->ch[1]->mx += p->lazy;            p->ch[1]->lazy += p->lazy;        }        p->lazy = 0;    }    if(p->tag != 0){        if(p->ch[0] != null) p->ch[0]->tag ^= 1;        if(p->ch[1] != null) p->ch[1]->tag ^= 1;        swap(p->ch[0],p->ch[1]);        p->tag = 0;    }}inline void rotate(Node *p,Node *x){    int k = p == x->ch[1];    Node *y = p->ch[k^1],*z = x->fa;    if(z->ch[0] == x) z->ch[0] = p;    if(z->ch[1] == x) z->ch[1] = p;    if(y != null) y->fa = x;    p->fa = z;p->ch[k^1] = x;    x->fa = p;x->ch[k] = y;    x->update();p->update();}inline bool isroot(Node *p){    return (p->fa->ch[0] != p && p->fa->ch[1] != p);}Node* sta[maxn];int top;inline void splay(Node *p){    push_down(p);    while(!isroot(p)){        Node *x = p->fa,*y = x->fa;        push_down(y);push_down(x);push_down(p);        if(isroot(x)) rotate(p,x);        else if((p == x->ch[0])^(x == y->ch[0])) rotate(p,x),rotate(p,y);        else rotate(x,y),rotate(p,x);    }p->update();}inline Node* Access(Node *u){    for(Node *v=null;u != null;v=u,u=u->fa)        splay(u),u->ch[1] = v,u->update();    return u;}inline void makeRt(Node *u){    Access(u);splay(u);u->tag ^= 1;}inline void link(Node *u,Node *v){    makeRt(u);u->fa = v;}inline void cut(Node *u,Node *v){    makeRt(u);Access(v);splay(v);    v->ch[0] = v->ch[0]->fa = null;    v->update();}inline Node* getRt(Node *u){    Access(u);splay(u);    while(u->ch[0] != null) u = u->ch[0];    splay(u);return u;}inline void inc(Node *u,Node *v,int w){    makeRt(u);Access(v);splay(v);    v->lazy += w;v->w += w;v->mx += w;}inline int query(Node *u,Node *v){    makeRt(u);Access(v);splay(v);    return v->mx;}int a[maxn],b[maxn];int main(){    int n;    while(scanf("%d",&n) != EOF){        init();        for(int i=1;i