P2056 [ZJOI2007]捉迷藏（线段树维护直径）

· · 题解

P2056 [ZJOI2007]捉迷藏

根据直径的性质，当合并两个点集时，新直径的端点一定是被合并的两个点集直径四个端点中的某两个。 那么我们可以用线段树维护区间直径（的端点）。对于可用的点，初值设为自己；否则设为 (-1,-1)。那么我们只需要一棵支持全局查找 \min ，单调修改的线段树即可。

求直径（两点间距离）需要求 lca。如果使用倍增/树剖，总复杂度就是 O(n\log^2n)的；如果使用ST表，复杂度则为 O(n\log n)。

注意：这种做法是基于贪心思想的，所以不能处理负边权

#include<bits/stdc++.h>
#define mid (l+r)/2
#define ls ro<<1
#define rs ro<<1|1
using namespace std;
namespace FGF
{
    int n,m;
    const int N=3e5+5;
    struct edg{
        int to,nxt,w;
    }e[N<<1];
    int dep[N],dis[N],fa[N],lo[N],st[N<<1][25],dfn[N],num,id[N],cnt,head[N];
    void add(int u,int v,int w)
    {
        cnt++;
        e[cnt].to=v;
        e[cnt].nxt=head[u];
        head[u]=cnt;
        e[cnt].w=w;
    }
    void dfs(int u,int f,int d)
    {
        dfn[u]=++num;id[num]=u;dep[num]=d;
        for(int i=head[u];i;i=e[i].nxt)
            if(e[i].to!=f)dis[e[i].to]=dis[u]+e[i].w,dfs(e[i].to,u,d+1),id[++num]=u,dep[num]=d;
    }
    void init()
    {
        lo[1]=0;
        for(int i=2;i<=num;i++)lo[i]=lo[i>>1]+1;
        for(int i=1;i<=num;i++)st[i][0]=i;
        for(int j=1;j<=lo[num];j++)
            for(int i=1;i<=num-(1<<j)+1;i++)
                st[i][j]=(dep[st[i][j-1]]<=dep[st[i+(1<<(j-1))][j-1]]? st[i][j-1]:st[i+(1<<(j-1))][j-1]);
    }
    int getlca(int x,int y)
    {
        int l=dfn[x],r=dfn[y];
        if(l>r)swap(l,r);
        int k=lo[r-l+1];
        return dep[st[l][k]]<=dep[st[r-(1<<k)+1][k]]? id[st[l][k]]:id[st[r-(1<<k)+1][k]];
    }
    int getdis(int x,int y)
    {
        return dis[x]+dis[y]-2*dis[getlca(x,y)];
    }
    struct tree{
        int u,v;
    }t[N<<4];
    void pushup(int ro)
    {
        if(t[ls].u==-1&&t[ls].v==-1){t[ro]=t[rs];return;}
        if(t[rs].u==-1&&t[rs].v==-1){t[ro]=t[ls];return;}
        if(getdis(t[ls].u,t[ls].v)>getdis(t[rs].u,t[rs].v))t[ro]=t[ls];else t[ro]=t[rs];
        if(getdis(t[ls].u,t[rs].u)>getdis(t[ro].u,t[ro].v))t[ro].u=t[ls].u,t[ro].v=t[rs].u;
        if(getdis(t[ls].u,t[rs].v)>getdis(t[ro].u,t[ro].v))t[ro].u=t[ls].u,t[ro].v=t[rs].v;
        if(getdis(t[ls].v,t[rs].u)>getdis(t[ro].u,t[ro].v))t[ro].u=t[ls].v,t[ro].v=t[rs].u;
        if(getdis(t[ls].v,t[rs].v)>getdis(t[ro].u,t[ro].v))t[ro].u=t[ls].v,t[ro].v=t[rs].v;
    }
    void build(int ro,int l,int r)
    {
        if(l==r)
        {
            t[ro].u=t[ro].v=l;
            return;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        pushup(ro);
    }
    void updat(int ro,int l,int r,int x)
    {
        if(l==r)
        {
            if(t[ro].u==-1&&t[ro].v==-1)t[ro].u=t[ro].v=x;
            else t[ro].u=t[ro].v=-1;
            return;
        }
        x<=mid? updat(ls,l,mid,x):updat(rs,mid+1,r,x);
        pushup(ro);
    }
    void work()
    {
        scanf("%d",&n);
        for(int i=1;i<n;i++)
        {
            int u,v,w=1;
            scanf("%d%d",&u,&v);
            add(u,v,w),add(v,u,w);
        }
        dfs(1,0,0);
        init();
        build(1,1,n);
        scanf("%d",&m);
        char s[5];int u;
        while(m--)
        {
            scanf("%s",s);
            if(s[0]=='C')scanf("%d",&u),updat(1,1,n,u);
            else 
            {
                if(t[1].u==-1||t[1].v==-1)puts("-1");
                else printf("%d\n",getdis(t[1].u,t[1].v));
            }
        }
    }
}
int main()
{
    FGF::work();
    return 0;
}