题解 P2056 【[ZJOI2007]捉迷藏 】

· · 题解

讲一下简单线段树做法。

首先，有一个结论:

现有集合S,T。设其直径点集为F(S),F(T)。则F(S\bigcup T)\subset F(S)\bigcup F(T)。

那么，根据这个结论，我们考虑利用线段树来维护区间直径。合并区间时直接暴力合并计算即可。

关于计算直径，需要知道两个点之间的lca。如果使用树链剖分或者倍增，则时间复杂度为O(n\log^2n)。如果使用st表，那么时间复杂度为O(n\log n)。

代码:

#include<bits/stdc++.h>
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
#define For(i,a,b) for(i=(a),i<=(b);++i)
#define Forward(i,a,b) for(i=(a),i>=(b);--i)
#define Chkmax(a,b) a=a>b?a:b

typedef unsigned int uint32;

inline uint32 getwd(void)
{
    static const uint32 BUFSIZE = 1048576;
    static char buf[BUFSIZE];
    static char *bufnow = buf;
    static char *bufmax = buf;
    if (bufnow == bufmax) {
        bufmax = buf + fread(buf, 1, BUFSIZE, stdin);
        bufnow = buf;
    }
    return *bufnow++;
}

inline void read(uint32 &x){
    static char k;k=getwd();x=0;
    while(!isdigit(k)&&k^'-')k=getwd();
    while(isdigit(k)){x=x*10+(k^48);k=getwd();}
}

inline void getopt(char &opt){for(opt=getwd();!isupper(opt);opt=getwd());}

inline void write(uint32 x)
{
    static uint32 sta[35],tp;
    if(!x){putchar(48),putchar('\n');return;}
    for(tp=0;x;x/=10)sta[++tp]=x%10;
    for(;tp;putchar(sta[tp--]^48));
    putchar('\n');
}
using namespace std;
void file()
{
#ifndef ONLINE_JUDGE
    freopen("practice.in","r",stdin);
    freopen("practice.out","w",stdout);
#endif
}

const uint32 MAXN=5e5+7;

static uint32 n,e,head[MAXN],m;

static struct edge
{
    uint32 v,nxt;
}p[MAXN<<1];

inline void add(uint32 u,uint32 v){p[++e]=(edge){v,head[u]};head[u]=e;}

static uint32 st[MAXN],dfn[MAXN],las[MAXN],fa[20][MAXN],dep[MAXN],re[MAXN];

void dfs(uint32 u,uint32 fr)
{
    re[dfn[u]=++e]=u;fa[0][u]=fr;dep[u]=dep[fr]+1;
    for(register uint32 v=head[u];v;v=p[v].nxt)if(p[v].v^fr)dfs(p[v].v,u);
    las[u]=e;
}

static uint32 Log[MAXN];

inline void init()
{
    read(n);
    static uint32 u,v;
    Rep(i,1,n-1)read(u),read(v),add(u,v),add(v,u);e=0;
    dfs(1,0);
    Rep(i,2,n)Log[i]=Log[i>>1]+1;
    Rep(j,1,Log[n])Rep(i,1,n)fa[j][i]=fa[j-1][fa[j-1][i]];
}

inline uint32 dist(uint32 u,uint32 v)
{
    u=re[u];v=re[v];
    static uint32 dps;dps=dep[u]+dep[v];
    if(dep[u]<dep[v])swap(u,v);
    for(;dep[u]-dep[v];u=fa[Log[dep[u]-dep[v]]][u]);
    if(u==v)return dps-2*dep[u];
    Repe(i,Log[dep[u]],0)if(fa[i][u]^fa[i][v])u=fa[i][u],v=fa[i][v];
    return dps-2*dep[u]+2;
}

namespace Segment_Tree
{
    static uint32 poi[MAXN<<2][3],dst[MAXN<<2];

    inline void pushup(uint32 h)
    {
        static uint32 dis;
        dst[h]=-1;poi[h][0]=poi[h][1]=poi[h][2]=0;
        if(dst[h<<1]==-1)
        {
            dst[h]=dst[h<<1|1],poi[h][0]=poi[h<<1|1][0];
            poi[h][1]=poi[h<<1|1][1],poi[h][2]=poi[h<<1|1][2];
        }
        else if(dst[h<<1|1]==-1)
        {
            dst[h]=dst[h<<1],poi[h][0]=poi[h<<1][0];
            poi[h][1]=poi[h<<1][1],poi[h][2]=poi[h<<1][2];
        }
        else
        {
            if(dst[h<<1]<dst[h<<1|1])
            {
                dst[h]=dst[h<<1|1],poi[h][0]=poi[h<<1|1][0];
                poi[h][1]=poi[h<<1|1][1],poi[h][2]=poi[h<<1|1][2];
            }
            else
            {
                dst[h]=dst[h<<1],poi[h][0]=poi[h<<1][0];
                poi[h][1]=poi[h<<1][1],poi[h][2]=poi[h<<1][2];
            }
            Rep(i,1,poi[h<<1][0])Rep(j,1,poi[h<<1|1][0])
                if((dis=dist(poi[h<<1][i],poi[h<<1|1][j]))>dst[h])
                    dst[h]=dis,poi[h][1]=poi[h<<1][i],poi[h][2]=poi[h<<1|1][j];
            poi[h][0]=2;
        }
    }

    void make_tree(uint32 h,uint32 l,uint32 r)
    {
        if(l==r)
        {
            st[l]=1;poi[h][0]=1;poi[h][1]=l;
            return;
        }
        uint32 mid=(l+r)>>1;
        make_tree(h<<1,l,mid);make_tree(h<<1|1,mid+1,r);
        pushup(h);
    }

    void modify(uint32 h,uint32 l,uint32 r,uint32 x)
    {
        if(l==r)
        {
            if(st[l])st[l]=poi[h][0]=poi[h][1]=0,dst[h]=-1;
            else st[l]=poi[h][0]=1,poi[h][1]=l,dst[h]=0;
            return;
        }
        static uint32 mid;mid=(l+r)>>1;
        x<=mid?modify(h<<1,l,mid,x):modify(h<<1|1,mid+1,r,x);
        pushup(h);
    }

    static uint32 dsts,pi[3];

    inline void Combine(uint32 h)
    {
        static uint32 u,v,dis;
        if(!poi[h][0])return;
        if(!pi[0])pi[0]=poi[h][0],pi[1]=poi[h][1],pi[2]=poi[h][2],dsts=dst[h];
        else
        {
            if(dst[h]>dsts)dsts=dst[h],u=poi[h][1],v=poi[h][2];
            else u=pi[1],v=pi[2];
            Rep(i,1,pi[0])Rep(j,1,poi[h][0])
                if((dis=dist(pi[i],poi[h][j]))>dsts)
                    dsts=dis,u=pi[i],v=poi[h][j];
            pi[0]=2;pi[1]=u;pi[2]=v;
        }
    }

    void query(uint32 h,uint32 l,uint32 r,uint32 x,uint32 y)
    {
        if(l>=x&&r<=y)
        {
            Combine(h);
            return;
        }
        uint32 mid=(l+r)>>1;
        if(x<=mid)query(h<<1,l,mid,x,y);
        if(y>mid)query(h<<1|1,mid+1,r,x,y);
    }
}
using namespace Segment_Tree;

inline void solve()
{
    read(m);
    static char x;
    static uint32 rt;
    make_tree(1,1,n);
    Rep(i,1,m)
    {
        getopt(x);read(rt);
        if(x=='C')modify(1,1,n,dfn[rt]);
        else
        {
            pi[0]=pi[1]=pi[2]=0;dsts=-1;
            query(1,1,n,dfn[rt],las[rt]);
            ~dsts?write(dsts):(void)puts("-1");
        }
    }
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
}

int main()
{
    file();
    init();
    solve();
    return 0;
}