[ZJOI2007] 捉迷藏

idea1

可能会死掉的想法：考虑点分治维护每个分治中心x到达分治块内的个点距离，具体是用堆维护分治快内的x的儿子y到y的子树内的所有点距离（记为c[y]），取所有c[y]的top+e(x,y)放入x的堆里（记为b[x]），答案为所有b[x]的top+top2的最大值，可以在用一个堆维护（记为a）。

参考的实现，可以得到80分。

#include <queue>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <iostream>
using namespace std;

const int n=1e5+10;

struct erasableheap {
    std::priority_queue<int> a,b;
    void insert(int w) {a.push(w);}
    void erase(int w) {b.push(w);}
    int size() {return a.size()-b.size();}
    int top() {
        while(b.size()&&a.top()==b.top()) a.pop(),b.pop();
        return a.top();
    }
    int top2() {
        int top1=top(); erase(top1);
        int topt=top(); insert(top1);
        return topt;
    }
} a,b[n],c[n];

struct edge {
    int to,len,last;
} e[n<<1];

int n,q,val[n],tar[n];
int head[n];

void addedge(int x,int y,int w) {
    static int cnt=1;
    e[++cnt]=(edge){y,w,head[x]},head[x]=cnt;
    e[++cnt]=(edge){x,w,head[y]},head[y]=cnt;
}

namespace dbl {
    int fa[n][20],ds[n][20],dep[n];
    void pre(int x,int pa) {
        dep[x]=dep[fa[x][0]=pa]+1;
        for(int i=1; (1<<i)<=dep[x]; ++i) {
            fa[x][i]=fa[fa[x][i-1]][i-1];
            ds[x][i]=ds[x][i-1]+ds[fa[x][i-1]][i-1];
        }
        for(int i=head[x]; i; i=e[i].last) {
            if(e[i].to==pa) continue;
            ds[e[i].to][0]=e[i].len;
            pre(e[i].to,x);
        }
    }
    int getdis(int x,int y) {
        if(dep[x]<dep[y]) std::swap(x,y);
        int dif=dep[x]-dep[y],sum=0;
        for(int i=19; ~i; --i) 
            if((dif>>i)&1) sum+=ds[x][i],x=fa[x][i];
        if(x==y) return sum;
        for(int i=19; ~i; --i) {
            if(fa[x][i]!=fa[y][i]) {
                sum+=ds[x][i],x=fa[x][i];
                sum+=ds[y][i],y=fa[y][i];
            } 
        }
        return sum+ds[x][0]+ds[y][0];
    }
}

void tryinsb(int x,int dis) {
    if(b[x].size()==0) {
        if(!val[x]) a.insert(dis);
        b[x].insert(dis);
    } else if(b[x].size()==1) {
        if(!val[x]&&b[x].top()<dis) a.erase(b[x].top());
        b[x].insert(dis);
        a.insert(b[x].top()+b[x].top2());
    } else if(b[x].top2()<dis) {
        a.erase(b[x].top()+b[x].top2());
        b[x].insert(dis);
        a.insert(b[x].top()+b[x].top2());
    } else b[x].insert(dis);
}
void tryerab(int x,int dis) {
    if(!b[x].size()) return; // notice
    if(b[x].size()==1) {
        if(!val[x]) a.erase(dis);
        b[x].erase(dis);
    } else if(b[x].top2()<=dis) {
        a.erase(b[x].top()+b[x].top2());
        b[x].erase(dis);
        if(b[x].size()>1) a.insert(b[x].top()+b[x].top2());
        else if(!val[x]) a.insert(b[x].top());
    } else b[x].erase(dis);
}

int stk[n],top;
void whitetoblack(int d) {
    for(int i=tar[d]; i; i=tar[e[i^1].to]) stk[++top]=i;
    for(int&i=top; i>=1; --i) {
        int x=e[stk[i]^1].to;
        int y=e[stk[i]].to,dis=dbl::getdis(d,y);
        if(c[y].top()>dis) c[y].erase(dis);
        else if(c[y].size()>1&&c[y].top2()==dis) c[y].erase(dis);
        else {
            tryerab(x,dis+e[stk[i]].len); c[y].erase(dis);  
            if(c[y].size()) tryinsb(x,c[y].top()+e[stk[i]].len);
        }
    }
    if(b[d].size()==1) a.erase(b[d].top());
    val[d]=1; 
}
void blacktowhite(int d) {
    for(int i=tar[d]; i; i=tar[e[i^1].to]) stk[++top]=i;
    for(int&i=top; i>=1; --i) {
        int x=e[stk[i]^1].to;
        int y=e[stk[i]].to,dis=dbl::getdis(d,y);
        if(c[y].size()==0) c[y].insert(dis),tryinsb(x,dis+e[stk[i]].len);
        else if(c[y].top()>=dis) c[y].insert(dis);
        else {
            tryerab(x,c[y].top()+e[stk[i]].len); c[y].insert(dis);
            tryinsb(x,dis+e[stk[i]].len); 
        }
    }
    if(b[d].size()==1) a.insert(b[d].top());
    val[d]=0;
}

int rt,sum,siz[n];
bool ban[n];
void getroot(int x,int fa) {
    static int f[n]={n+n};
    f[x]=0,siz[x]=1;
    for(int i=head[x]; i; i=e[i].last) {
        if(e[i].to==fa||ban[e[i].to]) continue;
        getroot(e[i].to,x);
        siz[x]+=siz[e[i].to];
        f[x]=std::max(f[x],siz[e[i].to]);
    }
    f[x]=std::max(f[x],sum-siz[x]);
    if(f[x]<f[rt]) rt=x;
}
void getc(int x,int fa,int dis,int top) {
    c[top].insert(dis);
    for(int i=head[x]; i; i=e[i].last) {
        if(e[i].to==fa||ban[e[i].to]) continue;
        getc(e[i].to,x,dis+e[i].len,top);
    }
}
void build(int x) {
    ban[x]=true;
    for(int i=head[x]; i; i=e[i].last) {
        if(ban[e[i].to]) continue;
        getc(e[i].to,x,0,e[i].to);
        b[x].insert(c[e[i].to].top()+e[i].len);
    }
    for(int i=head[x]; i; i=e[i].last) {
        if(ban[e[i].to]) continue;
        rt=0;
        sum=siz[e[i].to];
        getroot(e[i].to,x);
        tar[rt]=i;
        build(rt);
    }
    if(b[x].size()>1) a.insert(b[x].top()+b[x].top2());
    else if(b[x].size()) a.insert(b[x].top());
}

int main() {
    scanf("%d",&n);
    for(int i=n,x,y; --i; ) {
        scanf("%d%d",&x,&y);
        addedge(x,y,1);
    }
    dbl::pre(1,0);
    sum=n;
    getroot(1,0);
    build(rt);  
    int white=n,q,x;
    char chr[5];
    scanf("%d",&q);
    while(q--) {
        scanf("%s",chr);
        if(*chr=='g') {
            if(!white) puts("-1");
            else if(white==1) puts("0");
            else printf("%d\n",std::max(0,a.top()));
        } else {
            scanf("%d",&x);
            if(!val[x]) --white,whitetoblack(x);
            else ++white,blacktowhite(x);
        }
    }
    return 0;
}

代码中的一个技巧：记录tar[x]表示上一级分治中心连向x所在子树的边的编号，这样就能在爬树时同时得到原树儿子(e[tar[i]].to)、边长(e[tar[i]].len)、和上一层的分治中心(e[tar[i]^1].to)。

但想法有一个缺陷：注意notice的那句，为什么会有这种情况出现？原来对于同一个y对应的x可能不唯一，且每种对应的意义不一样（因为对应x不同，分治块范围不同）。补救措施可以考虑建立分治树时将被对应多次的y拆开（拆开的点都对应原树上的‘y’节点），最坏情况下单点y会被拆成deg[y]个，但是处于极限状况的点个数不会太多，总点数仍是o(n)级别。

经过抢救的部分 90分弃坑了

int ycnt,ybel[n],myy[n],myx[n],myl[n];

void whitetoblack(int d) {
    for(int i=d; myx[i]; i=myx[i]) {
        int x=myx[i];
        int y=myy[i],dis=dbl::getdis(d,ybel[y]);        
        if(c[y].top()>dis) c[y].erase(dis);
        else if(c[y].size()>1&&c[y].top2()==dis) c[y].erase(dis);
        else {
            tryerab(x,dis+myl[i]); c[y].erase(dis);  
            if(c[y].size()) tryinsb(x,c[y].top()+myl[i]);
        }
    }
    if(b[d].size()==1) a.erase(b[d].top());
    val[d]=1; 
}
void blacktowhite(int d) {
    for(int i=d; myx[i]; i=myx[i]) { 
        int x=myx[i];
        int y=myy[i],dis=dbl::getdis(d,ybel[y]);        
        if(c[y].size()==0) c[y].insert(dis),tryinsb(x,dis+myl[i]);
        else if(c[y].top()>=dis) c[y].insert(dis);
        else {
            tryerab(x,c[y].top()+myl[i]); c[y].insert(dis);
            tryinsb(x,dis+myl[i]); 
        }
    }
    if(b[d].size()==1) a.insert(b[d].top());
    val[d]=0;
}

int rt,sum,siz[n];
bool ban[n];
void getroot(int x,int fa) {
    static int f[n]={n+n};
    f[x]=0,siz[x]=1;
    for(int i=head[x]; i; i=e[i].last) {
        if(e[i].to==fa||ban[e[i].to]) continue;
        getroot(e[i].to,x);
        siz[x]+=siz[e[i].to];
        f[x]=std::max(f[x],siz[e[i].to]);
    }
    f[x]=std::max(f[x],sum-siz[x]);
    if(f[x]<f[rt]) rt=x;
}
void getc(int x,int fa,int dis,int top) {
    c[top].insert(dis);
    for(int i=head[x]; i; i=e[i].last) {
        if(e[i].to==fa||ban[e[i].to]) continue;
        getc(e[i].to,x,dis+e[i].len,top);
    }
}
void build(int x) {
    ban[x]=true;
    for(int i=head[x]; i; i=e[i].last) {
        if(ban[e[i].to]) continue;
        
        ybel[++ycnt]=e[i].to;
        getc(e[i].to,x,0,ycnt);
        b[x].insert(c[ycnt].top()+e[i].len);
        
        rt=0;
        sum=siz[e[i].to];
        getroot(e[i].to,x);
        myx[rt]=x;
        myy[rt]=ycnt;
        myl[rt]=e[i].len;
        build(rt);
    }
    if(b[x].size()>1) a.insert(b[x].top()+b[x].top2());
    else if(b[x].size()) a.insert(b[x].top());
}

idea2

别人的不会死掉的想法：直接用c[y]维护在x的分治块内y的子树中的所有节点到x的距离，b[x]取所有c[y]的最大值，由于不在依赖原树上的父子关系，避免了一个y对应了多个x的情况。

总结

我看别人题解的时候就不该看一半