LCA-LCT

五月 16, 2018

蒟蒻的LCA

这是蒟蒻我现在会的唯一的动态树LCA

先access(u),splay(u),查看一下v所在splay的根是否为u，如果是的话，那么 LCA(u,v)=vLCA(u,v)=v ；

然后access(v),此时再splay(v),查询一下u所在splay中的根节点为是否为v，如果是的话那么 LCA(u,v)=uLCA(u,v)=u ;

否则的话splay(u), LCA(u,v)=fa[u]LCA(u,v)=fa[u] ;

这个结论是很显然的，如果 u,v 的LCA是他们中的某一个的话，那么假设，那么u一定在v到根节点的路径上，在第二步时，access(v)以后u就与v在一棵子树中，所以，所以第二个步骤成立。第一步同理。考虑第二种情况，如果 LCA(u,v)=tLCA(u,v)=t ，那么在前两步执行完后，u在splay的根的父节点一定在v所在的splay中，且splay(u)后, fa[u]==LCA(u,v)fa[u]==LCA(u,v) ;证毕。

贴上代码：

#include <algorithm> //STL通用算法
#include <cmath> //定义数学函数
#include <cstdio> //定义输入/输出函数
#include <iostream> //数据流输入/输出
#include <cstring> //字符串处理
#include <string> //字符串类
#include <ctime> //定义关于时间的函数
#define itn int
#define fro for
#define ll long long
#define reg register
#define inf 1234567890
/*#include <bitset> //STL位集容器
#include <cstype> //字符处理
#include <cerrno> //定义错误码
#include <complex> //复数类
#include <clocale> //定义本地化函数
#include <cstdlib> //定义杂项函数及内存分配函数
#include <deque> //STL双端队列容器
#include <exception> //异常处理类
#include <fstream> //文件输入/输出
#include <functional> //STL定义运算函数(代替运算符)
#include <limits> //定义各种数据类型最值常量
#include <list> //STL线性列表容器
#include <map> //STL映射容器
#include <iomanip> //参数化输入/输出
#include <ios> //基本输入/输出支持
#include <iosfwd> //输入/输出系统使用的前置声明
#include <istream> //基本输入流
#include <ostream> //基本输出流
#include <queue> //STL队列容器
#include <set> //STL集合容器
#include <sstream> //基于字符串的流
#include <stack> //STL堆栈容器
#include <stdexcept> //标准异常类
#include <streambuf> //底层输入/输出支持
#include <utility> //STL通用模板类
#include <vector> //STL动态数组容器
#include <cwchar.h>//宽字符处理及输入/输出
#include <cwctype.h> //宽字符分类*/

using namespace std;

int ans;

int max(int x,int y){return x>y?x:y;}

int min(int x,int y){return x<y?x:y;}

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

void write(int x)
{
    int buf[50];
    if (x<0) putchar('-'),x=-x;
    buf[0]=0;
    while (x) buf[++buf[0]]=x%10,x/=10;
    if (!buf[0]) buf[0]=1,buf[1]=0;
    while (buf[0]) putchar('0'+buf[buf[0]--]);
}

int fa[500500],ch[500500][3],key[500500],sum[500500],lazy[500500];
int stk[500500],top=0;

int notroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}

void pushr(int x){swap(ch[x][0],ch[x][1]);lazy[x]^=1;}

void pushup(int x){sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^key[x];}

void pushdown(int x)
{
    if (lazy[x])
    {
        if (ch[x][0]) pushr(ch[x][0]);
        if (ch[x][1]) pushr(ch[x][1]);
        lazy[x]=0;
    }
}

void rot(int x)
{
    int y=fa[x],z=fa[y],k=ch[y][1]==x,w=ch[x][!k];
    if (notroot(y)) ch[z][ch[z][1]==y]=x;
    ch[x][!k]=y;ch[y][k]=w;
    if (w) fa[w]=y;fa[y]=x;fa[x]=z;
    pushup(y);
}

void splay(int x)
{
    int y=x,z;top=0;
    stk[++top]=y;
    while (notroot(y)) stk[++top]=y=fa[y];
    while (top) pushdown(stk[top--]);
    while (notroot(x))
    {
        y=fa[x],z=fa[y];
        if (notroot(y))
            rot((ch[y][0]==x)^(ch[z][0]==y)?x:y);
        rot(x);
    }
    pushup(x);
}

int access(int root)
{
    int temp=0;
    while (root)
    {
        splay(root);
        ch[root][1]=temp;
        temp=root;
        root=fa[root];
    }
    return temp;
}

void makeroot(int x){access(x);splay(x);pushr(x);}

int findroot(int x)
{
    access(x);splay(x);
    while (ch[x][0]) pushdown(x),x=ch[x][0];
    return x;
}

void link(int x,int y){makeroot(x);if (findroot(y)!=x) fa[x]=y;}

int lca(int x,int y)
{
    access(x);splay(x);
    int u=y;
    while (notroot(u)) u=fa[u];
    if (u==x) return y;
    access(y);splay(y);
    u=x;
    while (notroot(u)) u=fa[u];
    if (u==y) return x;
    splay(x);
    return fa[x];
}

int main()
{
    int n=read(),m=read(),s=read();
    for (int i=1;i<n;i++)
    {
        int q=read(),w=read();
        makeroot(s);
        link(q,w);
    }
    while (m--)
    {
        int q=read(),w=read(); 
        makeroot(s);
        printf("%d\n",lca(q,w));
    }
    return 0;
}

查看评论