Chlience

【题解】BZOJ 1095 [ZJOI2007]捉迷藏Hide
Problem给定一棵树,开始时每个节点都是黑色有两个操作:询问最远的两个黑色节点的距离将某个节点反色Though...
扫描右侧二维码阅读全文
04
2019/01

【题解】BZOJ 1095 [ZJOI2007]捉迷藏Hide

Problem

给定一棵树,开始时每个节点都是黑色
有两个操作:

  1. 询问最远的两个黑色节点的距离
  2. 将某个节点反色

Thought

听说这题是动态点分治入门题???

首先考虑静态做法:直接点分治,维护重心到其子树中最远黑点的距离

而动态做法中,我们将分治过程中遍历到的重心按照其包含关系连接起来,那么就能得到一棵新树,也就是 点分树
显然的,对于点分树上的某个节点,以及它的子树来说,在原图上这个点便是其子树的重心,那么在统计答案时只需要遍历一遍点分树上的子树

点分树上的儿子节点必然属于原图上不同的子树,那么考虑从每个儿子节点处取一个离当前节点最远的点,最终答案就是离当前节点最远的两个点的距离和

所以维护两个堆,第一个维护当前节点 $x$ 点分树子树中的点到点分树中 $x$ 父亲节点在原图中的距离,第二个堆维护点分树中当前节点 $x$ 的子节点的第一个堆的最大值,也就是在原图不同子树中离 $x$ 最远的点的距离

当然,因为要计算 $n\log n$ 次两点间距离,为了 $bigger$,还是用前面讲到的 $LCA$ 转 $RMQ$ 的方法使其加速查询过程

最终答案就是每个节点的第二个堆的最大值 + 次大值,另外再开一个堆维护即可

修改的话子集随便 $yy$ 一下就出来了,只需要想一想每次修改的点对其点分树上祖先节点的影响即可

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
struct Priority_Queue {
    priority_queue <int> heap , del;
    int size() {return heap.size() - del.size();}
    void insert(int x) {heap.push(x);}
    void erase(int x) {del.push(x);}
    void pop() {
        while(!del.empty() && heap.top() == del.top()) {heap.pop(); del.pop();}
        heap.pop();
    }
    int top() {
        while(!del.empty() && heap.top() == del.top()) {heap.pop(); del.pop();}
        return heap.top();
    }
    int top2() {
        int fir = top(); pop();
        int sec = top(); insert(fir);
        return fir + sec;
    }
}h1[N] , h2[N] , ans;

struct Edge {
    int t , n;
    void add(int _t , int _n) {t = _t; n = _n;}
}e[N << 1] , E[N << 1];
int head[N] , tot , headE[N] , totE;

int pre[N];

int siz[N] , max_siz[N] , root;
bool vis[N];

int bintwo[22] , logtwo[N << 1];
int dfn[N << 1] , DFN , f[N << 1][22] , dep[N] , fst[N];

int n , m , num;
bool whi[N];
char opt[10];

void addedge(int , int);
void addEdge(int , int);
void getSize(int , int);
void getRoot(int , int , int);
void getDis(int , int);
void build(int);

void dfs(int , int);
void prepare();
int lca(int , int);
int dis(int , int);

void addAns(int);
void turnOn(int);
void turnOff(int);

int main() {
    num = n = read();
    for(int i = 1 ; i < n ; ++ i) {
        int u = read() , v = read();
        addedge(u , v); addedge(v , u);
    }
    
    getSize(1 , 0);
    getRoot(1 , 0 , siz[1]);
    int rt = root;
    build(rt);

    dfs(rt , 1);
    prepare();
    addAns(rt);
    
    m = read();
    while(m --) {
        scanf("%s" , opt);
        if(opt[0] == 'G') {
            if(num == 0) puts("-1");
            else if(num == 1) puts("0");
            else printf("%d\n" , ans.top());
        }
        else {
            int x = read();
            if(whi[x]) turnOff(x);
            else turnOn(x);
            whi[x] ^= 1;
        }
    }
    return 0;
}

void addedge(int u , int v) {
    e[++ tot].add(v , head[u]);
    head[u] = tot;
}
void addEdge(int u , int v) {
    E[++ totE].add(v , headE[u]);
    headE[u] = totE;
}
//**********
//d(ian)f(en)s(hu) time!!!
//**********
void getSize(int x , int fa) {
    siz[x] = 1;
    for(int i = head[x] ; i ; i = e[i].n)
        if(e[i].t != fa && !vis[e[i].t]) {
            getSize(e[i].t , x);
            siz[x] += siz[e[i].t];
        }
}
void getRoot(int x , int fa , int sum_siz) {
    max_siz[x] = 0;
    for(int i = head[x] ; i ; i = e[i].n)
        if(e[i].t != fa && !vis[e[i].t]) {
            getRoot(e[i].t , x , sum_siz);
            max_siz[x] = max(max_siz[x] , siz[e[i].t]);
        }
    max_siz[x] = max(max_siz[x] , sum_siz - siz[x]);
    if(!root || max_siz[x] < max_siz[root]) root = x;
}
void getDis(int x , int fa , int to) {
    h1[to].insert(dis(x ,pre[to]));
    for(int i = head[x] ; i ; i = e[i].n)
        if(e[i].t != fa && !vis[e[i].t])
            getDis(e[i].t , x , to);
}
//**********
//ST time!!!
//**********
void build(int x) {
    vis[x] = 1;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(vis[e[i].t]) continue;
        root = 0;
        getSize(e[i].t , x);
        getRoot(e[i].t , x , siz[e[i].t]);
        int rt = root;

        addEdge(x , rt);
        build(rt);
    }
    vis[x] = 0;
}
void dfs(int x , int deep) {
    fst[x] = ++ DFN; dep[x] = deep;
    f[DFN][0] = x;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(fst[e[i].t]) continue;
        dfs(e[i].t , deep + 1);
        ++ DFN;
        f[DFN][0] = x;
    }
}
void prepare() {
    bintwo[0] = 1;
    for(int i = 1 ; i <= 21 ; ++ i)
        bintwo[i] = bintwo[i - 1] << 1;
    logtwo[0] = - 1;
    for(int i = 1 ; i <= 200000 ; ++ i)
        logtwo[i] = logtwo[i / 2] + 1;
    for(int j = 1 ; j <= logtwo[n << 1] ; ++ j)
        for(int i = 1 ; i + bintwo[j] - 1 <= (n << 1) ; ++ i)
            f[i][j] = dep[f[i][j - 1]] < dep[f[i + bintwo[j - 1]][j - 1]] ? f[i][j - 1] : f[i + bintwo[j - 1]][j - 1];
}
int lca(int u , int v) {
    u = fst[u]; v = fst[v];
    if(u > v) swap(u , v);
    int len = logtwo[v - u + 1];
    return dep[f[u][len]] < dep[f[v - bintwo[len] + 1][len]] ? f[u][len] : f[v - bintwo[len] + 1][len];
}
int dis(int u , int v) {return dep[u] + dep[v] - 2 * dep[lca(u , v)];}
void addAns(int x) {
    vis[x] = 1;
    h2[x].insert(0);
    for(int i = headE[x] ; i ; i = E[i].n) {
        pre[E[i].t] = x;
        getDis(E[i].t , x , E[i].t);
        if(h1[E[i].t].size())
            h2[x].insert(h1[E[i].t].top());
        addAns(E[i].t);
    }
    if(h2[x].size() >= 2) ans.insert(h2[x].top2());
    vis[x] = 0;
}

void turnOn(int x) {
    -- num;
    if(h2[x].size() == 2) ans.erase(h2[x].top2());
    h2[x].erase(0);
    for(int i = x ; pre[i] ; i = pre[i]) {
        if(h2[pre[i]].size() >= 2) ans.erase(h2[pre[i]].top2());
        if(h1[i].size()) h2[pre[i]].erase(h1[i].top());
        h1[i].erase(dis(x , pre[i]));
        if(h1[i].size()) h2[pre[i]].insert(h1[i].top());
        if(h2[pre[i]].size() >= 2) ans.insert(h2[pre[i]].top2());
    }
}
void turnOff(int x) {
    ++ num;
    h2[x].insert(0);
    if(h2[x].size() == 2) ans.insert(h2[x].top2());
    for(int i = x ; pre[i] ; i = pre[i]) {
        if(h2[pre[i]].size() >= 2) ans.erase(h2[pre[i]].top2());
        if(h1[i].size()) h2[pre[i]].erase(h1[i].top());
        h1[i].insert(dis(x , pre[i]));
        if(h1[i].size()) h2[pre[i]].insert(h1[i].top());
        if(h2[pre[i]].size() >= 2) ans.insert(h2[pre[i]].top2());
    }
}
Last modification:January 13th, 2019 at 11:04 am

Leave a Comment