BZOJ4539: [Hnoi2016]树【LCA+主席树】

4539: [Hnoi2016]树

【题目描述】

传送门

【题解】

分三类讨论,如果询问的下标在同一个子树中(这里的子树表示模式树的子树),那么直接LCA。
我们将大树看成很多棵子树连城的,每个子树为一个节点。
当x和y相聚好的棵子树时,他们之间的子树之间跳过,所以每次跳的答案是一定的,可以对大树LCA。
然后对于祖先特殊处理一下。
要判断x所在子树是否y所在子树的祖先,特殊处理就可以了。

代码如下

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
typedef long long LL;
struct Edge{
    int tot,lnk[MAXN],son[MAXN<<1],nxt[MAXN<<1];
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
struct REAL{LL fa,x,L,R;}a[MAXN];
struct ZX_Tree{int x,L,R;}Tre[MAXN*20];
int n,m,Q,tot,Top,tim,Siz[MAXN],T[MAXN],P[MAXN],Dfn[MAXN],Fa[MAXN][20],Dep[MAXN],TFa[MAXN][20],TDep[MAXN];LL SFa[MAXN][20];
#include<cctype>
LL read(){
    LL ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
void DFS(int x,int fa){
    Dfn[x]=++tim;P[tim]=x;Fa[x][0]=fa;Siz[x]=1;Dep[x]=Dep[fa]+1;
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(E.son[j]!=fa) DFS(E.son[j],x),Siz[x]+=Siz[E.son[j]];
}
void INIT(){
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i<=n;i++) Fa[i][j]=Fa[Fa[i][j-1]][j-1];
}
LL LCA(int x,int y){
    if(Dep[x]<Dep[y]) swap(x,y);
    int Del=(Dep[x]-Dep[y]);LL Ans=0;
    for(int i=0;(1<<i)<=Del;i++) if((1<<i)&Del) x=Fa[x][i],Ans+=(1<<i);
    if(x==y) return Ans;
    for(int i=log2(n);i>=0;i--)
    if(Fa[x][i]!=Fa[y][i]) x=Fa[x][i],y=Fa[y][i],Ans+=1<<i<<1;
    return Ans+2;
}
void Insert(int lst,int &rt,int L,int R,int p){
    rt=++tot;Tre[rt]=Tre[lst];Tre[rt].x++;
    if(L<R){
        int mid=(R+L)>>1;
        if(p<=mid) Insert(Tre[lst].L,Tre[rt].L,L,mid,p);
        else Insert(Tre[lst].R,Tre[rt].R,mid+1,R,p);
    }
}
int Query(int u,int v,int L,int R,LL p){
    if(L==R) return L;
    int Sum=Tre[Tre[v].L].x-Tre[Tre[u].L].x,mid=(R+L)>>1;
    if(Sum<p) return Query(Tre[u].R,Tre[v].R,mid+1,R,p-Sum);
    else return Query(Tre[u].L,Tre[v].L,L,mid,p);
}
int Fnd(LL x,int L,int R){
    for(int mid=(R+L)>>1;L<=R;mid=(R+L)>>1){
        if(a[mid].L<=x&&x<=a[mid].R) return mid;
        if(a[mid].R<x) L=mid+1;else R=mid-1;
    }
    return -1;
}
void ININT(){
    for(int j=1;(1<<j)<=Top;j++)
    for(int i=1;i<=Top;i++) TFa[i][j]=TFa[TFa[i][j-1]][j-1],SFa[i][j]=SFa[i][j-1]+SFa[TFa[i][j-1]][j-1];
}
LL LCAT(int &x,int &y){
    if(TDep[x]<TDep[y]) swap(x,y);
    int Del=(TDep[x]-TDep[y]);LL Ans=0;
    for(int i=0;(1<<i)<=Del;i++) if((1<<i)&Del) Ans+=SFa[x][i]+(1<<i),x=TFa[x][i];
    for(int i=log2(Top);i>=0;i--)
    if(TFa[x][i]!=TFa[y][i]) Ans+=(1<<i<<1)+SFa[x][i]+SFa[y][i],x=TFa[x][i],y=TFa[y][i];
    return Ans+2;
}
LL LCAT1(int &x,int y){
    int Del=(TDep[x]-TDep[y]-1);LL Ans=0;
    for(int i=0;(1<<i)<=Del;i++) if((1<<i)&Del) Ans+=SFa[x][i]+(1<<i),x=TFa[x][i];
    return Ans;
}
int main(){
    n=read(),m=read(),Q=read();
    for(int i=1,x,y;i<n;i++) x=read(),y=read(),E.Add(x,y),E.Add(y,x);
    DFS(1,0);INIT();
    for(int i=1;i<=n;i++) Insert(T[i-1],T[i],1,MAXN,P[i]);
    a[++Top]=(REAL){0,1,1,Siz[1]};
    for(int i=1;i<=m;i++){
        LL x=read(),y=read();
        a[++Top]=(REAL){y,x,a[Top-1].R+1,a[Top-1].R+Siz[x]};
        int Rot=Fnd(y,1,Top-1);
        TFa[Top][0]=Rot;TDep[Top]=TDep[Rot]+1;
        SFa[Top][0]=LCA(a[Rot].x,Query(T[Dfn[a[Rot].x]-1],T[Dfn[a[Rot].x]+Siz[a[Rot].x]-1],1,MAXN,y-a[Rot].L+1));
    }
    ININT();
    for(int i=1;i<=Q;i++){
        LL x=read(),y=read();
        int Rotx=Fnd(x,1,Top),Roty=Fnd(y,1,Top);
        if(TDep[Rotx]<TDep[Roty]) swap(x,y),swap(Rotx,Roty);
        int fx=Rotx,fy=Roty;LCAT(fx,fy);
        LL Ans=0;
        if(Rotx==Roty){
            x=Query(T[Dfn[a[Rotx].x]-1],T[Dfn[a[Rotx].x]+Siz[a[Rotx].x]-1],1,MAXN,x-a[Rotx].L+1);
            y=Query(T[Dfn[a[Roty].x]-1],T[Dfn[a[Roty].x]+Siz[a[Roty].x]-1],1,MAXN,y-a[Roty].L+1);
            Ans=LCA(x,y);
        }else
        if(fx==fy){
            Ans=LCA(a[Rotx].x,Query(T[Dfn[a[Rotx].x]-1],T[Dfn[a[Rotx].x]+Siz[a[Rotx].x]-1],1,MAXN,x-a[Rotx].L+1));
            Ans+=LCAT1(Rotx,Roty)+1;
            x=a[Rotx].fa;Rotx=Roty;
            x=Query(T[Dfn[a[Rotx].x]-1],T[Dfn[a[Rotx].x]+Siz[a[Rotx].x]-1],1,MAXN,x-a[Rotx].L+1);
            y=Query(T[Dfn[a[Roty].x]-1],T[Dfn[a[Roty].x]+Siz[a[Roty].x]-1],1,MAXN,y-a[Roty].L+1);
            Ans+=LCA(x,y);
        }else{
            fx=a[Rotx].x,fy=Query(T[Dfn[a[Rotx].x]-1],T[Dfn[a[Rotx].x]+Siz[a[Rotx].x]-1],1,MAXN,x-a[Rotx].L+1);
            Ans+=LCA(fx,fy);
            fx=a[Roty].x,fy=Query(T[Dfn[a[Roty].x]-1],T[Dfn[a[Roty].x]+Siz[a[Roty].x]-1],1,MAXN,y-a[Roty].L+1);
            Ans+=LCA(fx,fy);
            Ans+=LCAT(Rotx,Roty);
            x=a[Rotx].fa;y=a[Roty].fa;int Rot=TFa[Rotx][0];
            x=Query(T[Dfn[a[Rot].x]-1],T[Dfn[a[Rot].x]+Siz[a[Rot].x]-1],1,MAXN,x-a[Rot].L+1);
            y=Query(T[Dfn[a[Rot].x]-1],T[Dfn[a[Rot].x]+Siz[a[Rot].x]-1],1,MAXN,y-a[Rot].L+1);
            Ans+=LCA(x,y);
        }
        printf("%lld\n",Ans);
    }
    return 0;
}

发表评论

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

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部