【题目描述】
Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲 藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道 可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。
我们将以如下形式定义每一种操作：
C(hange) i 改变第i个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。
【输入格式】
第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b，表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如上文所示。
【输出格式】
对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出0；若所有房间的灯都开着，输出-1。
【样例输入】
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G
【样例输出】
4
3
3
4
【提示】
对于20%的数据， N ≤50, M ≤100；
对于60%的数据， N ≤3000, M ≤10000；
对于100%的数据， N ≤100000, M ≤500000。
这道题有三种做法。
我这里用线段树维护了一个括号序列。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
const int INF=;
int cnt,fir[maxn],nxt[maxn*],to[maxn*];
void addedge(int a,int b){
nxt[++cnt]=fir[a];
fir[a]=cnt;
to[cnt]=b;
}
int c[maxn];
int ID[maxn],rID[maxn*],tot;
struct Node{
int a,b,l1,l2,r1,r2,dis;
void Init(int p){
dis=-INF;a=b=;
if(rID[p]==-)b=;
if(rID[p]==-)a=;
if(rID[p]>&&c[rID[p]])
l1=l2=r1=r2=;
else
l1=l2=r1=r2=-INF;
}
void Push_up(Node l,Node r){
int a1=l.a,b1=l.b,a2=r.a,b2=r.b;
if(b1>=a2)a=a1,b=b1+b2-a2;
else a=a1+a2-b1,b=b2; dis=max(l.dis,r.dis);
dis=max(dis,max(l.r1+r.l2,l.r2+r.l1)); r1=max(r.r1,max(l.r1+b2-a2,l.r2+a2+b2));
r2=max(r.r2,l.r2+a2-b2); l1=max(l.l1,max(a1-b1+r.l1,a1+b1+r.l2));
l2=max(l.l2,r.l2+b1-a1);
}
}tr[(maxn*)<<]; void DFS(int x,int fa){
rID[++tot]=-;
rID[++tot]=x;
ID[x]=tot; for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa)
DFS(to[i],x);
rID[++tot]=-;
} void Build(int x,int l,int r){
if(l==r){
tr[x].Init(l); return;
}
int mid=(l+r)>>;
Build(x<<,l,mid);
Build(x<<|,mid+,r);
tr[x].Push_up(tr[x<<],tr[x<<|]);
} void Modify(int x,int l,int r,int g){
if(l==r){
tr[x].Init(l);
return;
}
int mid=(l+r)>>;
if(mid>=g)Modify(x<<,l,mid,g);
else Modify(x<<|,mid+,r,g);
tr[x].Push_up(tr[x<<],tr[x<<|]);
}
int n,Q,x;
char op[];
int main(){
#ifndef ONLINE_JUDGE
freopen("hide.in","r",stdin);
freopen("hide.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=;i<=n;i++)c[i]=;
for(int i=,a,b;i<n;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
} DFS(,);
Build(,,tot); scanf("%d",&Q);
while(Q--){
scanf("%s",op);
if(op[]=='C'){
scanf("%d",&x);
(c[x])?n--:n++;c[x]^=;
Modify(,,tot,ID[x]);
}
else{
if(n==)printf("-1\n");
else if(n==)printf("0\n");
else printf("%d\n",tr[].dis);
}
}
return ;
}
然后我又用点分治+堆的方法AC了一遍。
先按点分治访问 rt 节点的顺序建 fa 边，每次改一个点只要延 fa 边一路改上去就可以了。
关于开三个堆：
A：最终的答案。
B：对于每个点，都有一个对应的B类堆，B中最多只有此节点的子节点个数的元素，B中元素为该点子节点的C堆的堆顶。
C：对于每个点，都有一个对应的C类堆，堆中记录的是每一个子树中的节点对此点的 fa 的贡献。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=; struct Heap{
priority_queue<int>A,B;
void Insert(int x){A.push(x);}
void Delete(int x){B.push(x);}
void Pop(){
while(B.size()&&A.top()==B.top())
A.pop(),B.pop();
A.pop();
}
int Size(){return A.size()-B.size();}
int Max(){
while(B.size()&&A.top()==B.top())
A.pop(),B.pop();
if(!A.size())return ;
return A.top();
}
int Max2(){
if(Size()<)return ;
int p=Max(),ret;Pop();ret=Max();
Insert(p);return ret;
}
}A,B[maxn],C[maxn]; int fir[maxn],nxt[maxn*],to[maxn*],cnt;
void addedge(int a,int b){nxt[++cnt]=fir[a];to[cnt]=b;fir[a]=cnt;} int tot,ID[maxn],dep[maxn];
int Min[maxn*][],mm[maxn*];
void DFS(int x,int fa){
Min[ID[x]=++tot][]=dep[x];
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa){
dep[to[i]]=dep[x]+;
DFS(to[i],x);
Min[++tot][]=dep[x];
}
} int Dis(int x,int y){
if(ID[x]>ID[y])swap(x,y);
int k=mm[ID[y]-ID[x]+];
int ret=min(Min[ID[x]][k],Min[ID[y]-(<<k)+][k]);
return dep[x]+dep[y]-*ret;
} bool vis[maxn];
int sz[maxn],son[maxn],rt,N;
void Get_RT(int x,int fa){
sz[x]=;son[x]=;
for(int i=fir[x];i;i=nxt[i])
if(!vis[to[i]]&&to[i]!=fa){
Get_RT(to[i],x);
sz[x]+=sz[to[i]];
son[x]=max(son[x],sz[to[i]]);
}
son[x]=max(son[x],N-sz[x]);
if(!rt||son[rt]>son[x])rt=x;
} int fa[maxn];
void Div(int x,int f){
vis[x]=true;fa[x]=f;
for(int i=fir[x];i;i=nxt[i])
if(!vis[to[i]]){
rt=;N=sz[to[i]];
Get_RT(to[i],);
Div(rt,x);
}
} int light[maxn];
void Turn_OFF(int p,int x){
if(p==x){
B[x].Insert();
if(B[x].Size()==)
A.Insert(B[x].Max());
}
if(!fa[p])return;
int f=fa[p],mx=C[p].Max(),dis=Dis(f,x);
C[p].Insert(dis);
if(mx<dis){
int mt=B[f].Max()+B[f].Max2(),sz=B[f].Size();
if(C[p].Size()!=)
B[f].Delete(mx); B[f].Insert(dis);
if(mt<B[f].Max()+B[f].Max2()){
if(sz>=)A.Delete(mt);
if(B[f].Size()>=)A.Insert(B[f].Max()+B[f].Max2());
}
}
Turn_OFF(f,x);
} void Turn_ON(int p,int x){
if(p==x){
B[p].Delete();
if(B[p].Size()==)
A.Delete(B[p].Max());
}
if(!fa[p])return;
int f=fa[p],dis=Dis(f,x),mx;
C[p].Delete(dis);mx=C[p].Max();
if(mx<dis){
int mt=B[f].Max()+B[f].Max2(),sz=B[f].Size();
B[f].Delete(dis);
if(C[p].Size())
B[f].Insert(mx);
if(sz>=&&mt>B[f].Max()+B[f].Max2()){
if(sz>=)A.Delete(mt);
if(B[f].Size()>=)A.Insert(B[f].Max()+B[f].Max2());
}
}
Turn_ON(fa[p],x);
} int main(){
#ifndef ONLINE_JUDGE
freopen("hide.in","r",stdin);
freopen("hide.out","w",stdout);
#endif
int n;
scanf("%d",&n);
for(int i=,a,b;i<n;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}
DFS(,);mm[]=-;
for(int i=;i<=tot;i++){
if((i&(i-))==)mm[i]=mm[i-]+;
else mm[i]=mm[i-];
}
for(int k=;k<=mm[tot];k++)
for(int i=;i+(<<k)-<=tot;i++)
Min[i][k]=min(Min[i][k-],Min[i+(<<(k-))][k-]);
N=n;rt=;
Get_RT(,);
Div(rt,); for(int i=;i<=n;i++)
Turn_OFF(i,i); char op[];
int Q,tot=n,x;
scanf("%d",&Q);
while(Q--){
scanf("%s",op);
if(op[]=='C'){
scanf("%d",&x);
if(light[x])Turn_OFF(x,x);
else Turn_ON(x,x);
light[x]^=;
}
else{
if(tot<)
printf("%d\n",tot-);
else
printf("%d\n",A.Max());
}
}
return ;
}