BZOJ1095 Hide 捉迷藏 分治

时间:2022-06-01 20:21:36

%%%
http://blog.csdn.net/qq_34454069/article/details/78757007

题目

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");
            else
                printf("%d\n",*ans.rbegin());
        }
        else{
            scanf("%d",&a);
            if(light[a])
                turn_off(a);
            else
                turn_on(a);
        }
        if(i!=m)
            scanf("\n");
    }
}
int main()
{
    init();
    solve();
}