码农场
染色：给定一颗黑白树，请快速执行①将给定节点颜色翻转②求给定节点到最近的白色节点距离。
4.6划分、解决、合并：分治法
树上的分治法
重心分解后，对每个子树root维护一个优先队列que，维护子树中各白点到root的距离。这样染黑色时可以快速从que中找到仍然是白色的第一个点。如果不用que，只用一个元素Path的话，染白色固然没问题，染黑色就麻烦了。
查询x时，遍历x所属子树root，按如下方式更新答案
ans = min(ans, dist(x, root) + dist_white(root)); // x到根节点+根节点到白点
至于如何求dist，可以参考POJ 1986 Distance Queries 题解《挑战程序设计竞赛》，用LCA快速实现。
另外需注意查询次数可能非常多，需要预处理出所有的重心，而不要来一个查询求一次重心。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define MAX_V 100004
#define MAX_LOG_V 16
#define INF 0x3f3f3f3f
vector<int> G[MAX_V];
// 重心分割
int subtree_size[MAX_V], centroid[MAX_V]; // -1未初始化，-2没有上级子树
void compute_subtree_size(int v, int p)
{
subtree_size[v] = 1;
for (int i = 0; i < G[v].size(); ++i)
{
int to = G[v][i];
if (to != p && centroid[to] == -1)
{
compute_subtree_size(to, v);
subtree_size[v] += subtree_size[to];
}
}
}
void search_centroid(int v, int p, int n, int prev_centroid)
{
for (int i = 0; i < G[v].size(); ++i)
{
int to = G[v][i];
if (to != p && centroid[to] == -1 && 2 * subtree_size[to] > n)
{
search_centroid(to, v, n, prev_centroid);
return;
}
}
centroid[v] = prev_centroid;
for (int i = 0; i < G[v].size(); ++i)
{
int to = G[v][i];
if (centroid[to] == -1)
{
compute_subtree_size(to, -1);
search_centroid(to, v, subtree_size[to], v);
}
}
}
void init_centroid(int root)
{
memset(centroid, -1, sizeof centroid);
compute_subtree_size(root, -1);
search_centroid(root, -1, subtree_size[root], -2);
}
struct Path
{
int to, dist;
inline bool operator<(const Path &other) const
{
return dist > other.dist;
}
};
// LCA
int parent[MAX_LOG_V][MAX_V]; // 向上走2^k步所到的节点（超过根时记为-1）
int depth[MAX_V]; // 节点的深度
void dfs(int v, int p, int d)
{
parent[0][v] = p;
depth[v] = d;
for (int i = 0; i < G[v].size(); i++)
{
if (G[v][i] != p)
dfs(G[v][i], v, d + 1);
}
}
// 预处理
void init_lca(int V)
{
dfs(0, -1, 0);
// 预处理出parent
for (int k = 0; k + 1 < MAX_LOG_V; k++)
{
for (int v = 0; v < V; v++)
{
if (parent[k][v] < 0)
parent[k + 1][v] = -1;
else
{
parent[k + 1][v] = parent[k][parent[k][v]];
}
}
}
}
// 计算u和v的LCA
int lca(int u, int v)
{
// 让u和v向上走到同一深度
if (depth[u] > depth[v])
swap(u, v);
for (int k = 0; k < MAX_LOG_V; k++)
{
if ((depth[v] - depth[u]) >> k & 1)
{
v = parent[k][v];
}
}
if (u == v)
return u;
// 利用二分搜索计算LCA
for (int k = MAX_LOG_V - 1; k >= 0; k--)
{
if (parent[k][u] != parent[k][v])
{
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
int dist(int u, int v)
{
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
priority_queue<Path> que[MAX_V]; // que[centroid] := 中心centroid离子树中某个白点的路径
bool white[MAX_V];
int dist_white(int x)
{
priority_queue<Path> &q = que[x];
while (!q.empty())
{
Path cur = q.top();
if (!white[cur.to])
{
q.pop();
}
else
{
return cur.dist; // 最近的白点
}
}
return INF;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("err.txt", "w", stderr);
#endif
int N, Q;
scanf("%d", &N);
for (int i = 1, u, v; i < N; ++i)
{
scanf("%d %d", &u, &v);
--u, --v;
G[u].push_back(v);
G[v].push_back(u);
}
init_centroid(1);
init_lca(N);
scanf("%d", &Q);
int op, x;
while (Q--)
{
scanf("%d %d", &op, &x);
--x;
if (op == 0)
{
white[x] = !white[x];
if (white[x])
{
int root = x;
while (root != -2)
{
que[root].push(Path{x, dist(x, root)}); // 记录白点
root = centroid[root];
}
}
}
else
{
int ans = INF, root = x;
while (root != -2)
{
ans = min(ans, dist(x, root) + dist_white(root)); // x到根节点+根节点到白点
root = centroid[root];
}
printf("%d\n", ans == INF ? -1 : ans);
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stderr);
#endif
return 0;
}
知识共享署名-非商业性使用-相同方式共享：码农场 » SPOJ QTREE5 Query on a tree V 题解《挑战程序设计竞赛》