[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的情况。
总结
我看别人题解的时候就不该看一半