2018.09.16 bzoj3757: 蘋果樹（樹上莫隊）

傳送門

一道樹上莫隊。

先用跟bzoj1086一樣的方法給樹分塊。

分完之後就可以莫隊了。

但是兩個詢問之間如何轉移呢？

感覺很難受啊。

我們定義 S(u,v) S ( u , v ) 表示u->v這條路徑的點集， T(u,v) T ( u , v ) 表示 S(u,v) S ( u , v ) xor x o r lca(u,v) l c a ( u , v ) ，同時我們令上一個詢問是 S(predu,predv) S ( p r e d u , p r e d v ) 。

對于 T(u,v) T ( u , v ) 有一個恒等式：

T(u,v)=S(root,u) T ( u , v ) = S ( r o o t , u ) xor x o r S(root,v) S ( r o o t , v )

是以有：

T(predu,predv)=S(root,predu) T ( p r e d u , p r e d v ) = S ( r o o t , p r e d u ) xor x o r S(root,predv) S ( r o o t , p r e d v )

是以有：

T(u,v) T ( u , v ) xor x o r T(predu,predv)=S(root,u) T ( p r e d u , p r e d v ) = S ( r o o t , u ) xor x o r S(root,v) S ( r o o t , v ) xor x o r S(root,predu) S ( r o o t , p r e d u ) xor x o r S(root,predv) S ( r o o t , p r e d v )

是以有：

T(u,v)=T(predu,predv) T ( u , v ) = T ( p r e d u , p r e d v ) xor x o r T(predu,v) T ( p r e d u , v ) xor x o r T(u,predv) T ( u , p r e d v )

那麼更新就比較容易了。

代碼：

#include<bits/stdc++.h>
#define N 100005
#define sig 24
using namespace std;
int n,m,rt,sum,ans[N],blo[N],dfn[N],dep[N],first[N],cnt,blos,top,fa[N][sig],mul[N],block,tot,stk[N],tim[N],col[N];
bool vis[N];
struct edge{int v,next;}e[N<<];
struct Q{int u,v,a,b,id;}q[N];
inline bool cmp(Q a,Q b){return blo[a.u]==blo[b.u]?dfn[a.v]<dfn[b.v]:blo[a.u]<blo[b.u];}
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline void dfs(int p){
    dfn[p]=++tot,dep[p]=dep[fa[p][]]+;
    int tmp=top;
    for(int i=;i<sig;++i)
        if(dep[p]<mul[i])break;
        else fa[p][i]=fa[fa[p][i-]][i-];
    for(int i=first[p];i;i=e[i].next){
        int v=e[i].v;
        if(v==fa[p][])continue;
        fa[v][]=p,dfs(v);
        if(top-tmp>=block){
            ++blos;
            while(top!=tmp)blo[stk[top--]]=blos;
        }
    }
    stk[++top]=p;
}
inline int lca(int x,int y){
    if(dep[x]<dep[y])x^=y,y^=x,x^=y;
    int tmp=dep[x]-dep[y];
    for(int i=;i<sig;++i)if(tmp&(<<i))x=fa[x][i];
    if(x==y)return x;
    for(int i=sig-;~i;--i)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][];
}
inline void update(int x){
    if(vis[x]){
        vis[x]=,--tim[col[x]];
        if(tim[col[x]]==)--sum;
    }
    else{
        vis[x]=,++tim[col[x]];
        if(tim[col[x]]==)++sum;
    }
}
inline void reverse(int x,int y){
    while(x!=y){
        if(dep[x]<dep[y])x^=y,y^=x,x^=y;
        update(x),x=fa[x][];
    }
}
inline int read(){
    int ans=;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<)+(ans<<)+(ch^),ch=getchar();
    return ans;
}
int main(){
    n=read(),m=read(),mul[]=,block=sqrt(n);
    for(int i=;i<=n;++i)col[i]=read();
    for(int i=;i<=n;++i){
        int u=read(),v=read();
        if(!u||!v)rt=u+v;
        else add(u,v),add(v,u);
    }
    for(int i=;i<sig;++i)mul[i]=mul[i-]<<;
    dfs(rt),++blos;
    while(top)blo[stk[top--]]=blos;
    for(int i=;i<=m;++i){
        q[i].u=read(),q[i].v=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
        if(dfn[q[i].u]>dfn[q[i].v])q[i].u^=q[i].v,q[i].v^=q[i].u,q[i].u^=q[i].v;
    }
    sort(q+,q+m+,cmp);
    int Lca=lca(q[1].u,q[1].v);
    reverse(q[1].u,q[1].v),update(Lca),ans[q[1].id]=sum;
    if(q[1].a!=q[1].b&&tim[q[1].a]&&tim[q[1].b])--ans[q[1].id];
    for(int i=;i<=m;++i){
        update(Lca),reverse(q[i-1].u,q[i].u),reverse(q[i-1].v,q[i].v);
        Lca=lca(q[i].u,q[i].v),update(Lca),ans[q[i].id]=sum;
        if(q[i].a!=q[i].b&&tim[q[i].a]&&tim[q[i].b])--ans[q[i].id];
    }
    for(int i=;i<=m;++i)printf("%d\n",ans[i]);
    return ;
}