「题解」「POI 2007」MEG-Megalopolis

题目链接:Luogu P3459/BZOJ 1103/POI 2007。

未完待续

题解

解法 A 树链剖分

思路

树链剖分板子题,时间复杂度 $ \Theta (n \log _ {2} ^ {2} n ) $ 。

代码

#include<cstdio>
#include<algorithm>
using std::swap;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=250000+5;

struct SegmentTree{
    #define lson (k<<1)
    #define rson (k<<1|1)
    #define mid ((l+r)>>1)
    struct Node{
        int val;
        int tag;
        inline Node(void){
            val=0,tag=0;
            return;
        }
        inline Node(reg int a,reg int b){
            val=a,tag=b;
            return;
        }
    };
    Node unit[MAXN<<2];
    inline void pushup(reg int k){
        unit[k].val=unit[lson].val+unit[rson].val;
        return;
    }
    inline void Build(reg int k,reg int l,reg int r){
        if(l==r){
            unit[k]=Node(1,0);
            return;
        }
        Build(lson,l,mid);
        Build(rson,mid+1,r);
        pushup(k);
        return;
    }
    inline void Update(reg int k,reg int l,reg int r,reg int pos){
        if(l==r&&l==pos){
            --unit[k].val;
            return;
        }
        if(pos<=mid)
            Update(lson,l,mid,pos);
        if(pos>mid)
            Update(rson,mid+1,r,pos);
        pushup(k);
        return;
    }
    inline int Query(reg int k,reg int l,reg int r,reg int L,reg int R){
        if(L<=l&&r<=R)
            return unit[k].val;
        reg int res=0;
        if(L<=mid)
            res+=Query(lson,l,mid,L,R);
        if(R>mid)
            res+=Query(rson,mid+1,r,L,R);
        return res;
    }
    #undef lson
    #undef rson
    #undef mid
};

int n,m;
int w[MAXN];
int cnt,head[MAXN],to[MAXN<<1],Next[MAXN<<1];
int fa[MAXN],dep[MAXN],size[MAXN],son[MAXN];
int Time,id[MAXN],rank[MAXN],top[MAXN];
SegmentTree T;

inline void Add_Edge(reg int,reg int);
inline void DFS1(reg int,reg int);
inline void DFS2(reg int,reg int,reg int);
inline int Sum(int,int);

int main(void){
    reg int i;
    n=read();
    for(i=1;i<n;++i){
        static int a,b;
        a=read(),b=read();
        Add_Edge(a,b);
        Add_Edge(b,a);
    }
    DFS1(1,0);
    DFS2(1,0,1);
    T.Build(1,1,n);
    m=read();
    for(i=1;i<=m+n-1;++i){
        static char ch;
        static int u,v;
        do
            ch=getchar();
        while(ch!='A'&&ch!='W');
        if(ch=='A'){
            u=read(),v=read();
            T.Update(1,1,n,id[v]);
        }
        if(ch=='W'){
            u=read();
            printf("%d\n",Sum(1,u)-1);
        }
    }
    return 0;
}

inline void Add_Edge(reg int u,reg int v){
    Next[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
    return;
}

inline void DFS1(reg int ID,reg int father){
    reg int i;
    size[ID]=1;
    fa[ID]=father;
    dep[ID]=dep[father]+1;
    for(i=head[ID];i;i=Next[i])
        if(to[i]!=father){
            DFS1(to[i],ID);
            size[ID]+=size[to[i]];
            if(size[son[ID]]<size[to[i]])
                son[ID]=to[i];
        }
    return;
}

inline void DFS2(reg int ID,reg int father,reg int topf){
    reg int i;
    id[ID]=++Time;
    rank[Time]=ID;
    top[ID]=topf;
    if(!son[ID])
        return;
    DFS2(son[ID],ID,topf);
    for(i=head[ID];i;i=Next[i])
        if(to[i]!=son[ID]&&to[i]!=father)
            DFS2(to[i],ID,to[i]);
    return;
}

inline int Sum(int x,int y){
    reg int res=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        res+=T.Query(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    return res+T.Query(1,1,n,id[x],id[y]);
}

解法 B DFS+树状数组

思路

不难发现 $ \text{DFS} $ 序中,每一颗子树都分别位于一个区间中,我们只要记下区间范围,就可以避免题目中分枝的问题,那么题目就可以转化成区间修改+单点查询了,用树状数组可以解决。

渐进时间复杂度为 $ \Theta ( n \log _ {2} n ) $ 。

代码

略。