并不对劲的bzoj1095:p2056:[ZJOI2007]捉迷藏-白红宇

并不对劲的bzoj1095:p2056:[ZJOI2007]捉迷藏

阅读量：4952 次

发布时间：2019-06-12

本文共 2728 字，大约阅读时间需要 9 分钟。

题目大意

给一\(n\)(\(n\leq10^5\))个点的一棵树，每个点有可能是黑色或白色，一开始所有点都是黑色，支持以下两种操作：

1.改变一个点的颜色

2.询问最远的黑色点对的距离

题解

据说是动态点分治板板题

考虑点分治，发现容斥略有难想

所以考虑边分治，用可删堆维护重心边两侧到重心边最远的黑点到重心边的距离

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #define rep(i,x,y) for(register int i=(x);i<=(y);++i)#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)#define view(u,k) for(int k=fir[u];~k;k=nxt[k])#define pb push_back#define ls (u<<1)#define rs (u<<1|1)#define maxn 100010#define maxnd (maxn<<1)#define maxm (maxnd<<1) using namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)&&ch!='-')ch=getchar(); if(ch=='-')f=-1,ch=getchar(); while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); return x*f;}void write(int x){ if(x==0){putchar('0'),putchar('\n');return;} int f=0;char ch[20]; if(x<0)putchar('-'),x=-x; while(x)ch[++f]=x%10+'0',x/=10; while(f)putchar(ch[f--]); putchar('\n'); return;}int siz[maxnd],tot,n,fir[maxnd],nxt[maxm],v[maxm],cntrd,m,d[20][maxn],maxd[maxnd<<2];int sumsiz,wt,minsiz,w[maxm],vis[maxm],lens[maxn],wtk[maxnd<<2],bacn[maxn],stat[maxn]; vector
                 
                  to[maxn];struct deq{ priority_queue
                  
                   yes,no; void push(int x){yes.push(x);} void del(int x){no.push(x);} int top(){while(!no.empty()&&yes.top()==no.top())yes.pop(),no.pop();return yes.top();} int size(){return yes.size()-no.size();}}q[maxnd<<2];void ade(int u1,int v1,int w1){v[cntrd]=v1,nxt[cntrd]=fir[u1],w[cntrd]=w1,fir[u1]=cntrd++;}void get2(int u,int fa){ int lim=to[u].size()-1,lst=u,f=0; rep(i,0,lim)if(to[u][i]!=fa) { if(f){tot++,ade(lst,tot,0),ade(tot,lst,0),lst=tot;} ade(lst,to[u][i],1),ade(to[u][i],lst,1);f=1; } rep(i,0,lim)if(to[u][i]!=fa)get2(to[u][i],u);}void getsiz(int u,int fa){ siz[u]=1; view(u,k)if(v[k]!=fa&&!vis[k]) { getsiz(v[k],u),siz[u]+=siz[v[k]]; int nowmax=max(sumsiz-siz[v[k]],siz[v[k]]); if(nowmax
                   
                    siz[vv]?nowsiz-siz[vv]:siz[uu],sv=siz[vv]>siz[uu]?nowsiz-siz[uu]:siz[vv]; vis[wt]=vis[wt^1]=1;wtk[u]=wt; getdis(uu,0,ls,len,0),getdis(vv,0,rs,len,0); getwt(ls,uu,su,len+1),getwt(rs,vv,sv,len+1); pu(u);}char S[5];void chg(int x){ int u=bacn[x],len=lens[x],fa=u>>1; while(fa) { if(stat[x])q[u].push(d[len-1][x]); else q[u].del(d[len-1][x]); pu(fa); u>>=1,len--,fa=(u>>1); }stat[x]^=1;}int main(){ n=read();memset(fir,-1,sizeof(fir));tot=n; rep(i,1,n-1){int x=read(),y=read();to[x].pb(y),to[y].pb(x);} get2(1,0),getwt(1,1,tot,0); m=read(); while(m--) { int x; scanf("%s",S); if(S[0]=='C'){x=read();chg(x);} else write(maxd[1]); } return 0;}