[文章目录]
Description
某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。 我们将以如下形式定义每一种操作： C(hange) i 改变第i个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。 N ≤100000, M ≤500000
动态点分治
维护每一块可行点到上一层的fa的距离的最大值，以及（每个儿子的块中可行点到自己的最大距离【每个不同儿子维护一个】）的最大值和次大值的和。
那么答案就是所有节点的两个不同儿子到自己的最大值的和（最大+次大），维护所有节点的答案的最大值。
以上用2n+1个可删除堆维护即可。
P.S.一定要封装，维护堆、删除堆、最大+次大
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
const int inf=0x3f3f3f3f;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int re=0; char f=0,ch=nc();
while(!isdigit(ch)) f|=(ch=='-'),ch=nc();
while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
return f?-re:re;
}
inline char s_read() {char re=nc(); while(re!='C'&&re!='G') re=nc(); return re;}
inline int Min(int x,int y){return x<y ? x:y;}
inline int Max(int x,int y){return x>y ? x:y;}
//********************************************************************
int n,head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
int tot,pos[N],dep[N],lca[N<<1][20],Log[N<<1],bin[20];
void dfs(int x,int pre)
{
dep[x]=dep[pre]+1; pos[x]=++tot; lca[tot][0]=dep[x];
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
dfs(to[i],x),lca[++tot][0]=dep[x];
}
inline int dis(int x,int y)
{
if(pos[x]>pos[y]) swap(x,y);
int lo=Log[pos[y]-pos[x]+1];
return dep[x]+dep[y]-(Min(lca[pos[x]][lo],lca[pos[y]-bin[lo]+1][lo])<<1);
}
//********************************************************************
int nn,rot,root,fa[N],msi[N],siz[N],ran[N],now1[N],now2[N];
bool vis[N],ope[N];
struct heap
{
priority_queue<int>he,del;
void rush(){while(!del.empty()&&del.top()==he.top()) del.pop(),he.pop();}
void push(int x){he.push(x);}
void era(int x){del.push(x);}
int siz(){return he.size()-del.size();}
int top(){rush(); return (siz()==0) ? -1 : he.top();}
int sec()
{
if(siz()<=1) return siz()-1;
rush(); int t=he.top(); he.pop();
rush(); int re=t+he.top(); he.push(t);
return re;
}
}h1[N],h2[N],ans;//h1:当前联通子图到父亲的长度集合 h2:儿子h1的top()集合+当前点 ans:h2的sec()集合
void getroot(int x,int pre)
{
siz[x]=1; msi[x]=0;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)
getroot(to[i],x),msi[x]=Max(msi[x],siz[to[i]]),siz[x]+=siz[to[i]];
msi[x]=Max(msi[x],nn-siz[x]);
if(msi[x]<msi[root]) root=x;
}
void Dfs(int x,int pre)
{
ran[++tot]=x,siz[x]=1;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)
Dfs(to[i],x),siz[x]+=siz[to[i]];
}
void build(int x,int pre)
{
fa[x]=pre; tot=0; Dfs(x,pre); vis[x]=1;
if(pre) for(int i=1;i<=tot;++i) h1[x].push(dis(pre,ran[i]));
now1[x]=h1[x].top(); int p;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]])
{
root=0,nn=siz[to[i]],getroot(to[i],x);
build(p=root,x); if(now1[p]!=-1) h2[x].push(now1[p]);
}
h2[x].push(0); now2[x]=h2[x].sec(); ans.push(now2[x]);
}
//********************************************************************
void Del(int x)
{
h2[x].era(0);
if(h2[x].sec()!=now2[x])
{
ans.era(now2[x]);
ans.push(now2[x]=h2[x].sec());
}
for(int p=x;p;p=fa[p]) if(fa[p])
{
h1[p].era(dis(fa[p],x));
if(h1[p].siz()==0||h1[p].top()!=now1[p])
{
if(now1[p]!=-1) h2[fa[p]].era(now1[p]);
if(h1[p].siz()==0) now1[p]=-1;
else h2[fa[p]].push(now1[p]=h1[p].top());
if(h2[fa[p]].sec()!=now2[fa[p]])
{
ans.era(now2[fa[p]]);
ans.push(now2[fa[p]]=h2[fa[p]].sec());
}
}
}
}
void Insert(int x)
{
h2[x].push(0);
if(h2[x].sec()!=now2[x])
{
ans.era(now2[x]);
ans.push(now2[x]=h2[x].sec());
}
for(int p=x;p;p=fa[p]) if(fa[p])
{
h1[p].push(dis(fa[p],x));
if(h1[p].siz()==0||h1[p].top()!=now1[p])
{
if(now1[p]!=-1) h2[fa[p]].era(now1[p]);
if(h1[p].siz()==0) now1[p]=-1;
else h2[fa[p]].push(now1[p]=h1[p].top());
if(h2[fa[p]].sec()!=now2[fa[p]])
{
ans.era(now2[fa[p]]);
ans.push(now2[fa[p]]=h2[fa[p]].sec());
}
}
}
}
int main()
{
n=read(); int i,j;
for(i=1;i<n;++i) add(read(),read());
dfs(1,0);
for(i=2;i<=tot;++i) Log[i]=Log[i>>1]+1;
for(i=0;i<=Log[tot];++i) bin[i]=1<<i;
for(i=1;i<=Log[tot];++i)
for(j=1;j+bin[i]-1<=tot;++j)
lca[j][i]=Min(lca[j][i-1],lca[j+bin[i-1]][i-1]);
msi[0]=inf,nn=n,getroot(1,0); rot=root; build(root,0);
int m=read(); char op;
while(m--)
{
op=s_read();
if(op=='G') printf("%d\n",ans.top());
else
{
i=read();
(ope[i]) ? Insert(i) : Del(i);
ope[i]^=1;
}
}
return 0;
}