Luogu P2056 [ZJOI2007]捉迷藏

动态点分治
先建出一颗点分树，然后维护。
对于每一个点维护两个堆，一个堆维护子树内所有点到分治父节点的距离最大值，一个堆维护一个点所有子树的第一个堆的最大值，再全局维护一个堆取所有分治重心的答案的最大值即可。
代码细节感人。。。
一个比较有用的trick就是用两个大根堆实现可删除的堆但是要开O2

#include <cstdio>
#include <queue>
#include <cstdlib>
using namespace std;
#define R register
#define LL long long
const int MAXN=5e5+10;
inline int max(int x,int y) { return x > y ? x : y; }
inline int min(int x,int y) { return x < y ? x : y; }
inline int read() {
	int x=0,f=1; char a=getchar();
	for(;a>‘9‘||a<‘0‘;a=getchar()) if(a==‘-‘) f=-1;
	for(;a>=‘0‘&&a<=‘9‘;a=getchar()) x=x*10+a-‘0‘;
	return x*f;
}
inline char getc() {
	char a=getchar();
	while(a!=‘C‘&&a!=‘G‘) a=getchar();
	return a;
}
inline void Print(int x) {
	if(x>9) Print(x/10); putchar(x%10+‘0‘);
}
inline void print(int x) {
	if(x<0) putchar(‘-‘),x=-x; Print(x); putchar(‘\n‘);
}
class Heap {
	private:
		priority_queue<int> q1,q2;
	public:
	inline void push(int x) { q1.push(x); }
	inline void erase(int x) { q2.push(x); }
	inline int top() {
		while(q2.size()&&q1.top()==q2.top()) q1.pop(),q2.pop();
		return q1.top();
	}
	inline void pop() {
		while(q2.size()&&q1.top()==q2.top()) q1.pop(),q2.pop();
		q1.pop();
	}
	inline int top2() {
		int mxv=top(); pop(); int res=top(); push(mxv); return res; 
	}
	inline int size() { return q1.size()-q2.size(); }
};
Heap h1[MAXN],h2[MAXN],h3;

int n;
int head[MAXN],cnt;
struct edge { int to,next; } e[MAXN];
inline void add(int x,int y) { e[++cnt]={y,head[x]}; head[x]=cnt; }

namespace Graph {
	int dep[MAXN],son[MAXN],siz[MAXN],fa[MAXN],top[MAXN];
	inline void dfs1(int x,int fx) {
		siz[x]=1; dep[x]=dep[fx]+1;fa[x]=fx;
		for(R int i=head[x];i;i=e[i].next) {
			int y=e[i].to; if(y==fx) continue;
			dfs1(y,x); siz[x]+=siz[y];
			if(siz[y]>siz[son[x]]) son[x]=y;
		}
	}
	inline void dfs2(int x,int topx) {
		top[x]=topx;
		if(son[x]) dfs2(son[x],topx);
		for(R int i=head[x];i;i=e[i].next) {
			int y=e[i].to;
			if(y==fa[x]||y==son[x]) continue;
			dfs2(y,y);
		}
	}
	inline void build() { dfs1(1,0); dfs2(1,1); }
	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 dist(int x,int y) {
		int lca=LCA(x,y);
		return dep[x]+dep[y]-dep[lca]*2;
	}
}
namespace Tree {
	int total;
	int vis[MAXN],rt,siz[MAXN],mx[MAXN];
	int fa[MAXN];
	inline void findrt(int x,int fx) {
		siz[x]=1; mx[x]=0;
		for(R int i=head[x];i;i=e[i].next) {
			int y=e[i].to;
			if(y==fx||vis[y]) continue;
			findrt(y,x);
			siz[x]+=siz[y];
			mx[x]=max(mx[x],siz[y]);
		}
		mx[x]=max(mx[x],total-siz[x]);
		if(mx[x]<=mx[rt]) rt=x;
	}
	inline void getdis(int x,int fx,int verx) {
		h1[rt].push(Graph::dist(x,verx));
		for(R int i=head[x];i;i=e[i].next) { 
			int y=e[i].to;
			if(vis[y]||y==fx) continue;
			getdis(y,x,verx);
		}
	}
	inline void build_tree(int x,int fx) {
		fa[x]=fx; vis[x]=1; h2[x].push(0); int sz=total;
		for(R int i=head[x];i;i=e[i].next) {
			int y=e[i].to; if(vis[y]) continue;
			if(siz[y]>siz[x]) total=sz-siz[x]; else total=siz[y];
			rt=0; findrt(y,0); getdis(rt,0,x);
			h2[x].push(h1[rt].top()); build_tree(rt,x); 
		}
		if(h2[x].size()>1) h3.push(h2[x].top()+h2[x].top2());
	}
	inline void build() {
		total=n; rt=0; mx[0]=1e9;
		findrt(1,0); build_tree(rt,0);	
	}
	inline void off(int x) {
		h2[x].push(0);
		if(h2[x].size()==2) h3.push(h2[x].top()+h2[x].top2());
		R int now=x;
		while(fa[now]) {
			int mxv=h1[now].size()?h1[now].top():-1;int dis=Graph::dist(x,fa[now]);
			h1[now].push(dis); 
			if(dis>mxv) {
				if(h2[fa[now]].size()>1) h3.erase(h2[fa[now]].top()+h2[fa[now]].top2());
				if(mxv^-1) h2[fa[now]].erase(mxv);
				h2[fa[now]].push(dis);
				if(h2[fa[now]].size()>1) h3.push(h2[fa[now]].top()+h2[fa[now]].top2());
			} 
			now=fa[now];
		}
	}
	inline void on(int x) {
		if(h2[x].size()==2) h3.erase(h2[x].top());
		h2[x].erase(0);	
		R int now=x;
		while(fa[now]) {
			if(h2[fa[now]].size()>1)  h3.erase(h2[fa[now]].top()+h2[fa[now]].top2());
			h2[fa[now]].erase(h1[now].top()); h1[now].erase(Graph::dist(x,fa[now]));
			if(h1[now].size()) h2[fa[now]].push(h1[now].top());
			if(h2[fa[now]].size()>1) h3.push(h2[fa[now]].top()+h2[fa[now]].top2());
			now=fa[now];
		}
	}
}
using namespace Tree;
int sta[MAXN];
int main() {
//	freopen("a.in","r",stdin);
	n=read(); int tot=n;
	int x,y;
	for(R int i=1;i<n;i++) { x=read(); y=read(); add(x,y); add(y,x); }
	Graph::build(); build();
	R int q=read();
	while(q--) {
		if(getc()==‘C‘) {
			int x=read();
			if(sta[x]) tot++,Tree::off(x);
			else tot--,Tree::on(x);
			sta[x]^=1;
		}
		else {
			if(tot<2) print(tot-1);
			else print(h3.top());
		}
	}
	return 0;
}

Luogu P2056 [ZJOI2007]捉迷藏

原文：https://www.cnblogs.com/HN-wrp/p/12828749.html