BZOJ1095 Hide 捉迷藏 分治

Hide 捉迷藏 分治"/>

BZOJ1095 Hide 捉迷藏 分治

%%%

题目

Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。
我们将以如下形式定义每一种操作：
C(hange) i 改变第i个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。
一句话题意：给出一棵树，分为黑、白点，初始都是黑点，进行一些操作，改变点的颜色，询问最远的两个黑点

题解

动态点分治板题？？？
分治树和本树之间（搅过来搅过去）以至于调了好久。。。而且作死地把s1的下表滚动，也搅了一会儿
首先构建分治重心树
对于分治树上每个点i，维护两个堆
s1维护i的子树所有的黑点到i的父亲的值
（显然，最多只有n个子树）
s2维护i的每个儿子的s1的top
再储存一个ans，维护答案（即每个点s2最大值+次大值），答案即为ans的top
对于每个更新操作，就从该点对应的分治树上的点往上更新s1、s2、ans
然而怎么求距离呢
网上大部分都是用倍增rmq
其实呢，我们可以直接在构建重心树的时候就求出来节点i到它在分治树上祖先的距离
（来自某老阴比大佬的算法）
而且呢，由于只需要维护最大值，所以用两个优先队列代替multiset会好一些
（如果想知道怎么用优先队列，好像我不能提供什么帮助）
好像不止一些。。。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<set>
#include<vector>
using namespace std;
#define itr multiset<int>::reverse_iterator
#define pp multiset<int>::iterator
const int N=100005,M=200005,P=100;
struct node{int v,nxt;
}edge[M];
multiset<int>s1[N],s2[N],ans;
int dist[N][P],dcnt[N];
int id[N][P],pos;
int head[N],mcnt;
bool vis[N];
stack<int>S;
int fa[N][P];
int rt[N];
int cnt[N],sz[N];
bool ban[N];
bool light[N];
int n;
int lcnt;
void dfs(int u,int fat){vis[u]=1;cnt[u]=0;sz[u]=1;S.push(u);for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(v==fat||ban[v])continue ;dfs(v,u);sz[u]+=sz[v];cnt[u]=max(cnt[u],sz[v]);}
}
void find_dist(int u,int fat,int rt,int d,int idd){dcnt[u]++;dist[u][dcnt[u]]=d+1;fa[u][dcnt[u]]=rt;id[u][dcnt[u]]=idd;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(ban[v]||v==fat)continue ;find_dist(v,u,rt,d+1,idd);}
}
int dfs1(int x,int rt){memset(vis,0,sizeof vis);dfs(x,-1);int u=0,v=1<<30;while(!S.empty()){int y=S.top();S.pop();cnt[y]=max(cnt[y],sz[x]-sz[y]);if(cnt[y]<v)u=y,v=cnt[y];}return u;
}
void find_g(int u){for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(ban[v])continue ;int x=dfs1(v,u);if(!x)continue ;pos++;find_dist(v,u,u,0,pos);ban[x]=1;find_g(x);}
}
void add_edge(node a[],int u,int v){mcnt++;a[mcnt].v=v;a[mcnt].nxt=head[u];head[u]=mcnt;
}
void update1(int x){itr it=s2[x].rbegin();if(it==s2[x].rend())return ;else{int maxx=*it;it++;if(it==s2[x].rend()){if(light[x]){pp del=ans.find(maxx);if(del!=ans.end())ans.erase(del);}}else{pp del=ans.find(maxx+(*it));if(del!=ans.end())ans.erase(del);}}
}
void update2(int x){itr it=s2[x].rbegin();if(it==s2[x].rend())return ;else{int maxx=*it;it++;if(it==s2[x].rend()){if(light[x])ans.insert(maxx);}else{ans.insert(maxx+(*it));}}
}
void turn_on(int x){update1(x);light[x]=1;lcnt++;update2(x);for(int i=dcnt[x];i>=1;i--){int idx=id[x][i],y=fa[x][i];update1(y);if(!s1[idx].empty()){pp del=s2[y].find(*s1[idx].rbegin());if(del!=s2[y].end())s2[y].erase(del);}s1[idx].insert(dist[x][i]);s2[y].insert(*s1[idx].rbegin());update2(y);}
}
void turn_off(int x){update1(x);light[x]=0;lcnt--;update2(x);for(int i=dcnt[x];i>=1;i--){int idx=id[x][i],y=fa[x][i];update1(y);pp del=s2[y].find(*s1[idx].rbegin());if(del!=s2[y].end())s2[y].erase(del);del=s1[idx].find(dist[x][i]);if(del!=s1[idx].end())s1[idx].erase(del);if(!s1[idx].empty())s2[y].insert(*s1[idx].rbegin());update2(y);}
}
void init(){scanf("%d",&n);for(int i=1;i<=n-1;i++){int u,v;scanf("%d%d",&u,&v);add_edge(edge,u,v);add_edge(edge,v,u);}int x=dfs1(1,0);ban[x]=1;find_g(x);for(int i=1;i<=n;i++){turn_on(i);}
}
void solve(){int m;scanf("%d\n",&m);for(int i=1;i<=m;i++){char c=getchar();int a;if(c=='G'){if(lcnt==0)printf("-1\n");else if(lcnt==1)printf("0\n");elseprintf("%d\n",*ans.rbegin());}else{scanf("%d",&a);if(light[a])turn_off(a);elseturn_on(a);}if(i!=m)scanf("\n");}
}
int main()
{init();solve();
}