BZOJ-5165: 树上倍增

[文章目录]

Description

现有一棵树。您需要写一个树上倍增算法,以实现如下操作:
A x 新建一个节点,将它作为x节点的儿子,编号为当前节点总数+1。
Q k p1 p2 p3.... 查询p1,p2,p3...这些节点的LCA。其中k表示查询节点的个数。最初树上只有一个节点,编号为1。多个节点的LCA定义为:这些节点的公共祖先中深度最大的。n≤3000000 k≤1000。询问<=1000

对于所有询问,我们统计出dfs序最小和最大的两个点,这两个点的lca即为答案。
对于所有询问,我们将询问的编号扔到询问对应的两个点上,之后按照节点编号从大到小缩点,将该点上的所有询问编号与其父亲的合并,合并过程中暴力扫两个编号集合,如果发现两个相同编号,那么该编号的lca就是父亲节点。
分析复杂度:
对于每次合并:
统计相同编号的复杂度是O(siz1*siz2)的,总复杂度相当于所有节点中任选两个的方案数,
合并的时候如果父亲为空,那么直接将集合送给父亲。反之,则进行合并,复杂度O(siz2),和上面的加上,等价于没有。
总复杂度 空间复杂度
虽然麻烦,但毕竟是一种方法,还是写了。当时是rank3 7900ms 还挺快。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define R register 
#define N 3001000 
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline char gc() {char ch=nc(); while(ch!='A'&&ch!='Q') ch=nc(); return ch;}
inline int read()
{
    int re=0; char ch=nc();
    while(!isdigit(ch)) ch=nc();
    while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
    return re;
}
int n=1,m,id[N],fa[N],q[1100][1100],z[2100][2100],tot,ans[1100];

int tim,in[N],out[N],head[N],to[N],nxt[N],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
void dfs(int x)
{
    in[x]=++tim;
    for(int i=head[x];i;i=nxt[i]) dfs(to[i]);
    out[x]=++tim;
}

int main()
{
    R int T=read(); int *x;
    while(T--)
    {
        if(gc()=='A') fa[++n]=read();
        else for(*q[++m]=read(),x=q[m]+*q[m];x!=q[m];--x) *x=read();
    }
    for(R int i=2;i<=n;++i) add(fa[i],i);
    dfs(1); int l,r,v1,v2,*y;
    for(R int i=1;i<=m;++i)
    {
        l=tim+1; r=0;
        for(x=q[i]+*q[i];x!=q[i];--x)
        {
            if(in[*x]<l) l=in[v1=*x];
            if(out[*x]>r) r=out[v2=*x];
        }
        if(v1==v2) ans[i]=v1;
        else
        {
            if(!id[v1]) id[v1]=++tot;
            z[id[v1]][++*z[id[v1]]]=i;
            if(!id[v2]) id[v2]=++tot;
            z[id[v2]][++*z[id[v2]]]=i;
        }
    }
    for(R int i=n;i>1;--i)
    {
        if(!id[v1=fa[i]]) id[v1]=id[i];
        else
        {
            l=id[i]; r=id[v1];
            for(x=z[l]+*z[l];x!=z[l];--x)
                for(y=z[r]+*z[r];y!=z[r];--y)
                    if(*x==*y) ans[*x]=v1;
            y=z[r];
            for(x=z[l]+*z[l];x!=z[l];--x)
                y[++*y]=*x;
        }
    }
    for(R int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注