欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[ZJOI2007] 捉迷藏

程序员文章站 2024-01-15 22:59:58
idea1 可能会死掉的想法:考虑点分治维护每个分治中心x到达分治块内的个点距离,具体是用堆维护分治快内的x的儿子y到y的子树内的所有点距离(记为C[y]),取所有C[y]的top+e(x,y)放入x的堆里(记为B[x]),答案为所有B[x]的top+top2的最大值,可以在用一个堆维护(记为A)。 ......

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的情况。

总结

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