BZOJ 1095: [ZJOI2007]Hide 捉迷藏(动态点分治)

解题思路

　　点分树其实就是在点分治的基础上，把重心连起来。这样树高是$log$的，可以套用数据结构进行操作。这道题是求最远距离，所以每个点维护两个堆，分别表示所管辖的子树的最远距离和到父节点的距离，再维护一个全局堆表示答案。修改的时候就从这个点开始暴力往上跳，每次修改到父节点的距离从而影响其父节点的子树的距离。时间复杂度$O(nlog^2n)$

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<queue>

using namespace std;

const int N=100005;

inline int rd(){

	int x=0;char ch=getchar();

	while(!isdigit(ch)) ch=getchar();

	while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return x;

}

void out(int x){

	if(!x) return ;out(x/10);putchar('0'+x%10);

}

inline int max(int x,int y){return x>y?x:y;}

int n,head[N],cnt,to[N<<1],nxt[N<<1],Min,siz[N],m;

int dep[N],g[N][25],fa[N],Sum,rt,tot;

bool vis[N],open[N];

struct Heap{

	priority_queue<int> del,Q;

	inline void Push(int x) {Q.push(x);}

	inline void Del(int x) {del.push(x);}

	inline int Top(){

		while(del.size() && Q.top()==del.top())

			del.pop(),Q.pop();

		return Q.top();

	}

	inline void Pop(){

		while(del.size() && Q.top()==del.top())

			del.pop(),Q.pop();

		Q.pop();

	}

	inline int sec_Top(){

		int tmp=Top(); Pop();

		int ret=Top(); Push(tmp);

		return ret;

	}

	inline int size(){return Q.size()-del.size();}

}f[N],c[N],ans;

inline void add(int bg,int ed){

	to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;

}	

int top[N],son[N],Fa[N];

void dfs(int x,int F){

	siz[x]=1; Fa[x]=F; int u,maxson=-1;

	for(int i=head[x];i;i=nxt[i]){

		u=to[i]; if(u==F) continue;

		dep[u]=dep[x]+1; dfs(u,x); siz[x]+=siz[u];

		if(siz[u]>maxson) maxson=siz[u],son[x]=u;

	}

}

void dfs2(int x,int topf){

	top[x]=topf;if(!son[x]) return ;

	dfs2(son[x],topf);int u;

	for(int i=head[x];i;i=nxt[i]){

		u=to[i];if(u==Fa[x] || u==son[x]) continue;

		dfs2(u,u);

	}

}

inline void init(){

	n=rd();int x,y;

	for(int i=1;i<n;i++){

		x=rd(),y=rd();

		add(x,y); add(y,x);

	}

	dfs(1,0); dfs2(1,1);

}

void dfs1(int x,int F){

	siz[x]=1; int u;

	for(int i=head[x];i;i=nxt[i]){

		u=to[i]; if(vis[u] || u==F) continue;

		dfs1(u,x); siz[x]+=siz[u];

	}

}

inline int LCA(int x,int y){

	while(top[x]!=top[y]){

		if(dep[top[x]]>dep[top[y]]) x=Fa[top[x]];

		else y=Fa[top[y]];

	}

	return dep[x]<dep[y]?x:y;

}

inline int DIS(int x,int y){

	if(!x || !y) return 0;

	int lca=LCA(x,y);

	return dep[x]+dep[y]-2*dep[lca];

}

void get_rt(int x,int F){

	int Max=0,u;

	for(register int i=head[x];i;i=nxt[i]){

		u=to[i]; if(u==F || vis[u]) continue;

		get_rt(u,x); Max=max(Max,siz[u]);

	}

	Max=max(Max,Sum-siz[x]);

	if(Max<Min) {Min=Max;rt=x;}

}

inline void get_dis(int x,int F,int pre){

	f[pre].Push(DIS(fa[pre],x));

	for(int i=head[x];i;i=nxt[i]){

		int u=to[i]; if(vis[u] || u==F) continue;

		get_dis(u,x,pre);

	}

}

inline void Insert(Heap &x){

	if(x.size()>1) ans.Push(x.Top()+x.sec_Top());

}

inline void Erase(Heap &x){

	if(x.size()>1) ans.Del(x.Top()+x.sec_Top());

}

int DFS(int x,int F){

	dfs1(x,0); Sum=siz[x]; Min=Sum+1; get_rt(x,0);

	int G=rt,son; fa[G]=F; vis[G]=1; Sum=0;

	get_dis(G,0,G); c[G].Push(0); rt=0;

	for(register int i=head[G];i;i=nxt[i]){

		int u=to[i]; if(vis[u]) continue;

		son=DFS(u,G); c[G].Push(f[son].Top());

	}

	Insert(c[G]);

	return G;

}

inline void solve_open(int x){

	Erase(c[x]); c[x].Del(0); Insert(c[x]);

	for(register int y=x;fa[y];y=fa[y]){

		Erase(c[fa[y]]);

		c[fa[y]].Del(f[y].Top());

		f[y].Del(DIS(x,fa[y]));

		if(f[y].size()) c[fa[y]].Push(f[y].Top());

		Insert(c[fa[y]]);

	}

}

inline void solve_close(int x){

	Erase(c[x]); c[x].Push(0); Insert(c[x]);

	for(register int y=x;fa[y];y=fa[y]){

		Erase(c[fa[y]]);

		if(f[y].size()) c[fa[y]].Del(f[y].Top());

		f[y].Push(DIS(x,fa[y]));

		c[fa[y]].Push(f[y].Top());

		Insert(c[fa[y]]);

	}

}

inline void work(){

	char c=getchar();while(c!='C' && c!='G') c=getchar();

	if(c=='G') {

		if(tot<=1) printf("%d\n",tot-1);

		else out(ans.Top()),putchar('\n');

	}

	else {

		int x=rd();

		if(!open[x]) tot--,solve_open(x),open[x]=1;

		else tot++,solve_close(x),open[x]=0;

	}

}

int main(){

	init(); DFS(1,0); m=rd(); tot=n;

	while(m--) work();

	return 0;

}

巴特西

BZOJ 1095: [ZJOI2007]Hide 捉迷藏(动态点分治)

解题思路

代码

最新文章

热门文章