![[SPOJ-QTREE4]Query on a tree IV 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180319e-540x400.jpg)
[SPOJ-QTREE4]Query on a tree IV 题解
题目地址：洛谷：【SP2666】QTREE4 – Query on a tre …
标签： 动态点分治
![[CFGym100633D]LWDB 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180316e-516x400.jpg)
![[ZJOI2007]捉迷藏 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180316d.jpg)
[ZJOI2007]捉迷藏 题解
题目地址：洛谷：【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;
}
