BZOJ1095 [ZJOI2007]Hide 捉迷藏

佚名 6年前 (2019-04-10) 随笔 1690人围观抢沙发百度已收录

题意

F.A.Qs	Home	Discuss	ProblemSet	Status	Ranklist	Contest	入门OJ	ModifyUser autoint	Logout	捐赠本站

Problem 1095. -- [ZJOI2007]Hide 捉迷藏

1095: [ZJOI2007]Hide 捉迷藏

Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 5824 Solved: 2505
[ Submit][ Status][ Discuss]

Description

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

Input

　　第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b，
表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如
上文所示。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Output

　　对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关
着灯的，输出0；若所有房间的灯都开着，输出-1。

Sample Input

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

Sample Output

4
3
3
4

HINT

对于100%的数据， N ≤100000, M ≤500000。

Source

[ Submit][ Status][ Discuss]
HOME Back 한국어 中文 فارسی English ไทย
版权所有 ©2008-2018 大视野在线测评 | 湘ICP备13009380号 Based on opensource project hustoj.

给定一棵树，一开始每个点都是黑点，多次改变某个点的状态或询问距离最远的两个黑点的距离

分析

参照PoPoQQQ的题解。

动态点分治题，hzwer写错了，看了好久才发现。

我们把分治过程中遍历过的重心都连起来，上一层的重心链接下一层的重心，可以得到一棵新的树，叫做点分树。下面我们开始讨论这棵新树。

显然这棵树的高度不会超过\(O(\log n)\)

然后我们每个节点开两个堆

第一个堆记录子树中所有节点到点分树上父亲节点的距离
第二个堆记录所有子节点的堆顶

那么一个节点的堆2中的最大和次大加起来就是子树中经过这个节点的最长链。

然后我们最后开一个全局的堆，记录所有堆2中最大值和次大值之和。那么全局的堆顶就是答案。

时间复杂度\(O((n+m)\log^2 n)\)

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=1e5+1;
int n,m;
vector<int> e[N];
int bin[20],lg[2*N],mn[18][N*2],dep[N],pos[N],dfn;
void dfs(int x,int fa){
    mn[0][pos[x]=++dfn]=dep[x];
    for(int i=0,y;i<e[x].size();++i){
        if((y=e[x][i])==fa) continue;
        dep[y]=dep[x]+1,dfs(y,x);
        mn[0][++dfn]=dep[x];
    }
}
il int rmq(int x,int y){
    x=pos[x],y=pos[y];
    if(x>y) swap(x,y);
    int t=lg[y-x+1];
    return min(mn[t][x],mn[t][y-bin[t]+1]);
}
il int dis(int x,int y){
    return dep[x]+dep[y]-2*rmq(x,y);
}

int root,sum,size[N],f[N],vis[N],fa[N];
void get_root(int x,int fa){
    size[x]=1,f[x]=0;
    for(int i=0,y;i<e[x].size();++i){
        if((y=e[x][i])==fa||vis[y]) continue;
        get_root(y,x);
        size[x]+=size[y],f[x]=max(f[x],size[y]);
    }
    f[x]=max(f[x],sum-size[x]);
    if(f[x]<f[root]) root=x;
}
void divide(int x,int f){
    fa[x]=f,vis[x]=1;
    for(int i=0,y;i<e[x].size();++i){
        if(vis[y=e[x][i]]) continue;
        root=0,sum=size[y],get_root(y,x),divide(root,x);
    }
}

struct heap{
    priority_queue<int> A,B;
    il void push(int x) {A.push(x);}
    il void erase(int x) {B.push(x);}
    il void pop(){
        while(B.size()&&A.top()==B.top()) A.pop(),B.pop();
        A.pop();
    }
    il int top(){
        while(B.size()&&A.top()==B.top()) A.pop(),B.pop();
        if(!A.size()) return 0;
        return A.top();
    }
    il int size() {return A.size()-B.size();}
    il int stop(){ // second top
        if(size()<2) return 0;
        int x=top();pop();
        int y=top();push(x);
        return y;
    }
}A,B[N],C[N];
int tot,clo[N];
void turn_off(int u,int v){
    if(u==v){
        B[u].push(0);
        if(B[u].size()==2)A.push(B[u].top());
    }
    if(!fa[u])return;
    int f=fa[u],D=dis(f,v),tmp=C[u].top();
    C[u].push(D);
    if(D>tmp){
        int mx=B[f].top()+B[f].stop(),size=B[f].size();
        if(tmp)B[f].erase(tmp);
        B[f].push(D);
        int now=B[f].top()+B[f].stop();
        if(now>mx){
            if(size>=2)A.erase(mx);
            if(B[f].size()>=2)A.push(now);
        }
    }
    turn_off(f,v);
}
void turn_on(int u,int v){
    if(u==v){
        if(B[u].size()==2)A.erase(B[u].top());
        B[u].erase(0);
    }
    if(!fa[u])return;
    int f=fa[u],D=dis(f,v),tmp=C[u].top();
    C[u].erase(D);
    if(D==tmp){
        int mx=B[f].top()+B[f].stop(),size=B[f].size();
        B[f].erase(D);
        if(C[u].top())B[f].push(C[u].top());
        int now=B[f].top()+B[f].stop();
        if(now<mx){
            if(size>=2)A.erase(mx);
            if(B[f].size()>=2)A.push(now);
        }
    }
    turn_on(f,v);
}

int main(){
    read(n);
    for(int i=1,u,v;i<n;++i){
        read(u),read(v);
        e[u].push_back(v),e[v].push_back(u);
    }
    // Range Minimum Query
    bin[0]=1;for(int i=1;i<20;++i) bin[i]=bin[i-1]<<1;
    lg[0]=-1;for(int i=1;i<n<<1;++i) lg[i]=lg[i>>1]+1;
    dfs(1,0);
    for(int i=1;i<=lg[dfn];++i)
        for(int j=1,t=dfn-bin[i]+1;j<=t;++j)
            mn[i][j]=min(mn[i-1][j],mn[i-1][j+bin[i-1]]);
    // Point Divide and Conquer
    root=0,f[0]=n,sum=n,get_root(1,0),divide(root,0);
    for(int i=1;i<=n;++i) C[i].push(0),clo[i]=1,turn_off(i,i),++tot;
    for(read(m);m--;){
        char ch[2];scanf("%s",ch);
        if(ch[0]=='G'){
            if(tot<=1) printf("%d\n",tot-1);
            else printf("%d\n",A.top());
        }
        else{
            int x=read<int>();
            if(clo[x]) turn_on(x,x),--tot;
            else turn_off(x,x),++tot;
            clo[x]^=1;
        }
    }
    return 0;
}