题目地址：洛谷：【P2056】[ZJOI2007]捉迷藏 – 洛谷、BZOJ：Problem 1095. — [ZJOI2007]Hide 捉迷藏

题目描述

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。

输入输出样例

输入样例#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

输出样例#1：

4
3
3
4

说明

对于20%的数据， N ≤50, M ≤100；
对于60%的数据， N ≤3000, M ≤10000； 对于100%的数据， N ≤100000, M ≤500000。

题解

解1：点分治

分析

这道题目里动态的是需要计入的点，那么我们就不能够一次分治将其求出来了。应用动态点分治的思想，我们可以先把点分树搞出来，然后在每一个重心统计子树信息。具体而言，我们这里要统计的是1.当前重心的所有儿子到重心的距离的集合；2.子树重心1信息最大值的集合；3.全局2信息中最大和次大值之和的集合，答案即是3集合的最大值。为了便于求最大值，我们可以考虑使用STL multiset或者堆来统计这些信息。每一次更新节点信息，我们要将其产生的影响向点分树中的父亲更新。具体而言，假如我们要关掉一个节点的灯，我们要向该节点1集合中插入0，向该节点的点分树祖先1集合插入该节点到祖先的距离，以儿子的1集合值更新祖先2集合值，以涉及的这条链上的点更新3集合的值。
具体的实现可以看代码，有部分注释，但是会有些绕。可以通过手动模拟一遍强行理解。
吐槽：洛谷这个题时限给1s谁过得去嘛！不过好像有人用SPOJ-QTREE4的代码过去了。

代码

下面的代码参考了hzwer的写法，因为自己并不知道怎么写，感谢hzwer学长。

// Code by KSkun, 2018/3
#include <cstdio>

#include <queue>

inline int max(int a, int b) {
    return a > b ? a : b;
} 

inline int min(int a, int b) {
    return a < b ? a : b;
} 

inline void swap(int &a, int &b) {
    register int t = a;
    a = b;
    b = t;
}

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'G' || c == 'C';
}

inline char readop() {
    register char c;
    while(!isop(c = fgc()));
    return c;
}

const int MAXN = 300005, INF = 1e9;

int n, m, ut, vt, xt, rt;
char op;
int siz[MAXN], dep[MAXN], msz[MAXN], sum, dfn[MAXN], clk, fa[MAXN], mn[MAXN][20], log2[MAXN], bin[20], tot;
bool vis[MAXN], status[MAXN];

struct Edge {
    int to, nxt;
} gra[MAXN << 1];
int head[MAXN], etot;

inline void addedge(int u, int v) {
    etot++;
    gra[etot].to = v;
    gra[etot].nxt = head[u];
    head[u] = etot;
}

struct Heap {
    std::priority_queue<int> heap, del;
    inline void push(int x) {
        heap.push(x);
    }
    inline void erase(int x) {
        del.push(x);
    }
    inline void pop() {
        while(del.size() && heap.top() == del.top()) heap.pop(), del.pop();
        heap.pop();
    }
    inline int top() {
        while(del.size() && heap.top() == del.top()) heap.pop(), del.pop();
        if(!heap.size()) return 0;
        return heap.top();
    }
    inline int size() {
        return heap.size() - del.size();
    }
    inline int secondTop() {
        if(size() < 2) return 0;
        int t = top(); pop();
        int t1 = top(); push(t);
        return t1;
    }
} A, B[MAXN], C[MAXN];

// 这里计算DFS序便于RMQ，以及处理每个点的深度，用根将子树序列夹起来可以实现查询最小值就能找到LCA的功能
inline void dfs(int u, int fa) {
    dfn[u] = ++clk;
    mn[dfn[u]][0] = dep[u];
    for(register int i = head[u]; i; i = gra[i].nxt) {
        register int v = gra[i].to;
        if(v == fa) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        mn[++clk][0] = dep[u];
    }
}

// 找重心
inline void getrt(int u, int fa) {
    siz[u] = 1;
    msz[u] = 0;
    for(register int i = head[u]; i; i = gra[i].nxt) {
        register int v = gra[i].to;
        if(v == fa || vis[v]) continue;
        getrt(v, u);
        siz[u] += siz[v];
        msz[u] = max(msz[u], siz[v]);
    }
    msz[u] = max(msz[u], sum - siz[u]);
    if(msz[u] < msz[rt]) rt = u;
}

// 点分治的DFS，用于构建点分树
inline void dac(int u, int f) {
    fa[u] = f;
    vis[u] = true;
    for(register int i = head[u]; i; i = gra[i].nxt) {
        register int v = gra[i].to;
        if(vis[v]) continue;
        sum = siz[v];
        rt = 0;
        getrt(v, u);
        dac(rt, u);
    }
}

// DFS序上的倍增RMQ
inline int rmq(int u, int v) {
    u = dfn[u]; v = dfn[v];
    if(u > v) swap(u, v);
    register int t = log2[v - u + 1];
    return min(mn[u][t], mn[v - bin[t] + 1][t]);
}

// 求两点间距离，基于上面的RMQ原理
inline int dis(int u, int v) {
    return dep[u] + dep[v] - 2 * rmq(u, v);
}

// 关灯时要做的事情
inline void 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;
    register int f = fa[u], d = dis(f, v), ct = C[u].top();
    C[u].push(d);
    if(d > ct) {
        register int mx = B[f].top() + B[f].secondTop(), size = B[f].size();
        if(ct) B[f].erase(ct);
        B[f].push(d);
        register int nmx = B[f].top() + B[f].secondTop();
        if(nmx > mx) {
            if(size >= 2) A.erase(mx);
            if(B[f].size() >= 2) A.push(nmx);
        }
    }
    off(f, v);
}

// 开灯时要做的事情
inline void 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;
    register int f = fa[u], d = dis(f, v), ct = C[u].top();
    C[u].erase(d);
        // 如果开灯影响到了2或3集合
    if(d == ct) {
        register int mx = B[f].top() + B[f].secondTop(), size = B[f].size();
        B[f].erase(d);
        if(C[u].top()) B[f].push(C[u].top());
        register int nmx = B[f].top() + B[f].secondTop();
        if(nmx < mx) {
            if(size >= 2) A.erase(mx);
            if(B[f].size() >= 2) A.push(nmx);
        }
    }
    on(f, v);
}

int main() {
        // 把2的若干次幂和log2的值预处理出来，减小常数
    bin[0] = 1;
    for(register int i = 1; i < 20; i++) bin[i] = bin[i - 1] << 1;
    log2[0] = -1;
    for(register int i = 1; i <= 200000; i++) log2[i] = log2[i >> 1] + 1;
    n = readint();
    for(register int i = 1; i < n; i++) {
        ut = readint(); vt = readint();
        addedge(ut, vt);
        addedge(vt, ut);
    }
    dfs(1, 0);
        // 倍增RMQ
    for(register int k = 1; k <= log2[clk]; k++) {
        for(register int i = 1; i <= clk; i++) {
            mn[i][k] = min(mn[i][k - 1], mn[i + bin[k - 1]][k - 1]);
        }
    }
    rt = 0;
    msz[0] = INF;
    sum = n;
    getrt(1, 0);
    dac(rt, 0);
    for(register int i = 1; i <= n; i++) C[i].push(0);
    for(register int i = 1; i <= n; i++) off(i, i), tot++; // 最初全部是关着灯的，给123集合设置初值
    m = readint();
    while(m--) {
        op = readop();
        if(op == 'G') {
            if(tot <= 1) printf("%d\n", tot - 1);
            else printf("%d\n", A.top());
        }
        if(op == 'C') {
            xt = readint();
            if(status[xt]) {
                off(xt, xt);
                tot--;
            } else {
                on(xt, xt);
                tot++;
            }
            status[xt] ^= 1;
        }
    }
    return 0;
}

解2：边分治

分析

类似QTREE4（题解：[SPOJ-QTREE4]Query on a tree IV 题解 | KSkun’s Blog），利用堆把每条中心边两端的dis统计出来，然后每个点记录它影响哪些中心边的答案。每个边计算最优的时候还要计算递归子结构的最优，最后询问的时候就可以不用单独查一次了。每次更新答案的时候要按照记录的倒序更新，因为倒序才是从底到顶的顺序。

代码

（其实是改的QTREE4的代码）

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'G' || c == 'C';
}

inline char readop() {
    char c;
    while(!isop(c = fgc()));
    return c;
}

const int MAXN = 1000005, INF = 2e9;

int n, q, col[MAXN], ans;

struct Edge {
    int to, w, nxt;
} gra[MAXN << 1], grao[MAXN << 1];
int head[MAXN], heado[MAXN], ecnt, ecnto;

inline void addedge(int u, int v, int w) {
    gra[ecnt] = Edge {v, w, head[u]}; head[u] = ecnt++;
}

inline void addedgeo(int u, int v, int w) {
    grao[ecnto] = Edge {v, w, heado[u]}; heado[u] = ecnto++;
}

inline void rebuild(int u, int fa) {
    int ff = 0;
    for(int i = heado[u]; ~i; i = grao[i].nxt) {
        int v = grao[i].to, w = grao[i].w;
        if(v == fa) continue;
        if(!ff) {
            addedge(u, v, w);
            addedge(v, u, w);
            ff = u;
        } else {
            int k = ++n;
            col[k] = 1;
            addedge(ff, k, 0);
            addedge(k, ff, 0);
            addedge(k, v, w);
            addedge(v, k, w);
            ff = k;
        }
        rebuild(v, u);
    }
}

bool del[MAXN << 1];
int ct, ctsiz, sum;
int siz[MAXN], msz[MAXN];

inline void calsiz(int u, int fa) {
    siz[u] = 1;
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(del[i >> 1] || v == fa) continue;
        calsiz(v, u);
        siz[u] += siz[v];
    }
}

inline void findct(int u, int fa) {
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(del[i >> 1] || v == fa) continue;
        findct(v, u);
        int vsiz = std::max(siz[v], sum - siz[v]);
        if(vsiz < ctsiz) {
            ct = i;
            ctsiz = vsiz;
        }
    }
}

struct DisData {
    int u, d;
    inline bool operator<(const DisData &rhs) const {
        return d < rhs.d;
    }
};

std::priority_queue<DisData> s[MAXN][2];
int cnt;

struct NodeData {
    int bel, side, dis;
};
std::vector<NodeData> ndata[MAXN];

inline void caldis(int u, int fa, int d, int t, int l) {
    if(!col[u]) {
        s[t][l].push(DisData {u, d}); ndata[u].push_back(NodeData {t, l, d});
    }
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to, w = gra[i].w;
        if(del[i >> 1] || v == fa) continue;
        caldis(v, u, d + w, t, l);
    }
}

int mx[MAXN], lch[MAXN], rch[MAXN], ctw[MAXN];

inline void update(int p) {
    while(!s[p][0].empty() && col[s[p][0].top().u]) s[p][0].pop();
    while(!s[p][1].empty() && col[s[p][1].top().u]) s[p][1].pop();
    if(s[p][0].empty() || s[p][1].empty()) mx[p] = 0;
    else mx[p] = s[p][0].top().d + ctw[p] + s[p][1].top().d;
    if(lch[p]) mx[p] = std::max(mx[p], mx[lch[p]]);
    if(rch[p]) mx[p] = std::max(mx[p], mx[rch[p]]);
}

inline int divide(int u) {
    calsiz(u, 0);
    ct = -1; ctsiz = INF; sum = siz[u]; findct(u, 0);
    if(ct == -1) return 0;
    int x = gra[ct].to, y = gra[ct ^ 1].to;
    del[ct >> 1] = true;
    int t = ++cnt;
    ctw[t] = gra[ct].w;
    caldis(x, 0, 0, t, 0); caldis(y, 0, 0, t, 1);
    lch[t] = divide(x); rch[t] = divide(y); 
    update(t);
    return t;
}

inline void setwhite(int u) {
    for(int i = ndata[u].size() - 1; i >= 0; i--) {
        NodeData d = ndata[u][i];
        s[d.bel][d.side].push(DisData {u, d.dis});
        update(d.bel);
    }
}

inline void setblack(int u) {
    for(int i = ndata[u].size() - 1; i >= 0; i--) {
        NodeData d = ndata[u][i];
        update(d.bel);
    }
}

int ut, vt, wt;
char op;

int main() {
    memset(head, -1, sizeof(head));
    memset(heado, -1, sizeof(heado));
    n = readint();
    int white = n;
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint();
        addedgeo(ut, vt, 1);
        addedgeo(vt, ut, 1);
    }
    rebuild(1, 0);
    divide(1);
    q = readint();
    while(q--) {
        op = readop();
        if(op == 'G') {
            if(!white) {
                puts("-1");
            } else if(white == 1) {
                puts("0");
            } else {
                printf("%d\n", mx[1]);
            }
        } else {
            ut = readint(); 
            col[ut] ^= 1;
            if(col[ut]) {
                setblack(ut);
                white--;
            } else {
                setwhite(ut);
                white++;
            }
        }
    }
    return 0;
}