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

题目大意

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

1.改变一个点的颜色

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

题解

据说是动态点分治板板题

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

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

代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#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<int>to[maxn];

struct deq

{

	priority_queue<int >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<minsiz)wt=k,minsiz=nowmax;

	}

}

void getdis(int u,int fa,int pos,int len,int dis)

{

	if(u<=n){d[len][u]=dis,q[pos].push(dis);}

	view(u,k)if(!vis[k]&&v[k]!=fa){getdis(v[k],u,pos,len,dis+w[k]);}

}

void pu(int u)

{

	maxd[u]=-1;

	if(q[ls].size()&&q[rs].size()){maxd[u]=q[ls].top()+q[rs].top()+w[wtk[u]];}

	maxd[u]=max(maxd[u],max(maxd[ls],maxd[rs]));

}

void getwt(int u,int nd,int nowsiz,int len)

{

	if(nowsiz==1){maxd[u]=-1;if(nd<=n)lens[nd]=len,bacn[nd]=u;return;}

	sumsiz=nowsiz,minsiz=tot+1,wt=-1,getsiz(nd,0);int uu=v[wt],vv=v[wt^1],su=siz[uu]>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;

}

一些感想

时隔一年，终于正式切了（之前是照着题解敲）这道题

相比于去年，我这个弱智猎人还是有一些进步的，至少也得是弱智猎人G

祝我在明天的紧急任务中狩猎愉快！

巴特西

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

题目大意

题解

代码

一些感想

最新文章

热门文章