SP8791 DYNALCA - Dynamic LCA

有一个森林最初由 \(n (1 \le n \le 100000)\) 个互不相连的点构成

你需要处理以下操作：

• link A B：添加从顶点A到B的边，使A成为B的子节点，其中保证A是一个根顶点，A和B在不同的树中。
• cut A：切断点A到其父节点的边，保证A是一个非根节点。
• lca A B：输出A和B的最近共同祖先，保证A和B在同一棵树中。

---

最开始我是这么写的

void LCA(int x,int y)

{

    access(x),splay(x),splay(y);

    while(par[y]) y=par[y],splay(y);

    printf("%d\n",y);

}

然后一直T

改成这个

int access(int now)

{

    int las=0;

    for(;now;las=now,now=fa)

        splay(now),rs=las;

    return las;

}

void LCA(int x,int y)

{

    access(x);

    printf("%d\n",access(y));

}

就过了

恩，需要虚实边转换，否则复杂度是假的

huyufeifei orz告诉我了这个问题

---

Code:

#include <cstdio>

#include <cctype>

#define fa par[now]

#define rs ch[now][1]

const int N=1e5+10;

template <class T>

inline void read(T &x)

{

    x=0;char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

int ch[N][2],par[N];

bool isroot(int now){return ch[fa][0]==now||ch[fa][1]==now;}

int identity(int now){return ch[fa][1]==now;}

void connect(int f,int now,int typ){ch[fa=f][typ]=now;}

void Rotate(int now)

{

    int p=fa,typ=identity(now);

    connect(p,ch[now][typ^1],typ);

    if(isroot(p)) connect(par[p],now,identity(p));

    else fa=par[p];

    connect(now,p,typ^1);

}

void splay(int now)

{

    for(;isroot(now);Rotate(now))

        if(isroot(fa))

            Rotate(identity(now)^identity(fa)?now:fa);

}

int access(int now)

{

    int las=0;

    for(;now;las=now,now=fa)

        splay(now),rs=las;

    return las;

}

void LCA(int x,int y)

{

    access(x);

    printf("%d\n",access(y));

}

void Link(int x,int y)

{

    access(x),splay(x);

    par[x]=y;

}

void cat(int x)

{

    access(x),splay(x);

    par[ch[x][0]]=0;

    ch[x][0]=0;

}

int main()

{

    int n,m;char op[23];

    read(n),read(m);

    for(int x,y,i=1;i<=m;i++)

    {

        scanf("%s",op);

        if(op[1]=='i') read(x),read(y),Link(x,y);

        else if(op[1]=='u') read(x),cat(x);

        else read(x),read(y),LCA(x,y);

    }

    return 0;

}

---

2019.3.10