[SPOJ-QTREE5]Query on a tree V 题解
![[SPOJ-QTREE5]Query on a tree V 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180320a.jpg "180320a")
题目地址：洛谷：【SP2939】QTREE5 – Query on a tree V – 洛谷、SPOJ：SPOJ.com – Problem QTREE5
SPOJ QTREE系列：
- [SPOJ-QTREE]Query on a tree 题解（树链剖分）
- [SPOJ-QTREE2]Query on a tree II 题解（树链剖分）
- [SPOJ-PT07J]Query on a tree III 题解（主席树）
- [SPOJ-QTREE3]Query on a tree again! 题解（树链剖分）
- [SPOJ-QTREE4]Query on a tree IV 题解（点分治/边分治）
- [SPOJ-QTREE5]Query on a tree V 题解（边分治）
- [SPOJ-QTREE6]Query on a tree VI 题解（LCT）
- [SPOJ-QTREE7]Query on a tree VII 题解（LCT）
题目描述
You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N. We define dist(a, b) as the number of edges on the path from node a to node b.
Each node has a color, white or black. All the nodes are black initially.
We will ask you to perfrom some instructions of the following form:
- 0 i : change the color of i-th node(from black to white, or from white to black).
- 1 v : ask for the minimum dist(u, v), node u must be white(u can be equal to v). Obviously, as long as node v is white, the result will always be 0.
给一棵树，最开始点都是黑色，操作1.改变点的颜色2.求离点v最近的白点距离。
输入输出格式
输入格式：
In the first line there is an integer N (N <= 100000)
In the next N-1 lines, the i-th line describes the i-th edge: a line with two integers a b denotes an edge between a and b.
In the next line, there is an integer Q denotes the number of instructions (Q <= 100000)
In the next Q lines, each line contains an instruction “0 i” or “1 v”
输出格式：
For each “1 v” operation, print one integer representing its result. If there is no white node in the tree, you should write “-1”.
输入输出样例
输入样例#1：
10 1 2 1 3 2 4 1 5 1 6 4 7 7 8 5 9 1 10 10 0 6 0 6 0 6 1 3 0 1 0 1 1 3 1 10 1 4 1 6
输出样例#1：
2 2 2 3 0
题解
本题可以从QTREE4的边分写法改过来。
本题维护堆的方法与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;
}
const int MAXN = 200005, 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;
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) {
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 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();
}
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);
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);
}
}
inline int query(int u) {
int mn = INF;
for(int i = ndata[u].size() - 1; i >= 0; i--) {
NodeData d = ndata[u][i];
if(!s[d.bel][d.side].empty()) mn = std::min(mn, s[d.bel][d.side].top().d + d.dis);
if(!s[d.bel][d.side ^ 1].empty()) mn = std::min(mn, s[d.bel][d.side ^ 1].top().d + d.dis + ctw[d.bel]);
}
return mn;
}
int op, ut, vt;
int main() {
memset(head, -1, sizeof(head));
memset(heado, -1, sizeof(heado));
n = readint();
int white = 0;
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 = readint();
ut = readint();
if(op == 1) {
if(!white) {
puts("-1");
} else if(col[ut]) {
puts("0");
} else {
printf("%d\n", query(ut));
}
} else {
col[ut] ^= 1;
if(!col[ut]) {
setblack(ut);
white--;
} else {
setwhite(ut);
white++;
}
}
}
return 0;
}
