===
Index
简介
树分治可以用来解决如下问题:
- 在一棵树上有多少条路径的长度正好是k
- 在一棵树上有多少条路径的xor和为k，或者所有xor路径的总和。
- 更新一个节点从黑到白或从白到黑，查询一个节点到白节点的最短路径
通过对原树进行重心分解，得到一颗新树,该树满足如下性质
- 新树包含原树的所有节点，原树中的每个节点都是一些子树的重心。
- 新树的高度最多 log(N)
- 原树中任意两点 x,y 的路径，在新树中都被分成 (x, z) 和 (z, y)两段，其中z = lca(x,y)
最近的红色节点
一棵由n个节点组成的树。编号从1到n。初始，仅有节点1是红色，其他节点涂成蓝色，有m次查询。
- 将一个给定节点涂成红色
- 给定节点u，计算距离给定节点最近的红色节点并输出最短距离。
分析
#include <bits/stdc++.h>
using namespace std;
const int INF = int(1e9) + 5;
template<typename T>
struct TreeCD {
using edge = pair<int, T>;
int n;
vector<vector<edge>> g;
vector<int> dep, siz,cent_pa, subrt, nodes;
vector<vector<pair<int, int>>> cent_dis;
TreeCD(int n) : n(n), g(n), dep(n), siz(n), cent_pa(n, -1), subrt(n),cent_dis(n){}
void add_edge(int u, int v, T w = 0) {
assert(u != v);
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
void erase_edge(int from, int to) {
for (edge &e : g[from]) if (e.first == to) {
swap(e, g[from].back());
g[from].pop_back();
return;
}
assert(false);
}
int dfs(int u, int pa = -1, int sub = -1, T w = 0) {
if (pa < 0) {sub = u; nodes.clear();}
dep[u] = pa < 0 ? 0 : dep[pa] + 1, siz[u] = 1,subrt[u] = sub;
nodes.push_back(u);
for (auto &[v, w1] : g[u]) if (v != pa)
siz[u] += dfs(v, u, pa < 0 ? v : sub, w + w1);
return siz[u];
}
int centroid(int root) {
int n = dfs(root);
bool ok;
do {
ok = false;
for (auto &[v, _] : g[root]) if (siz[v] < siz[root] && 2 * siz[v] >= n) {
root = v, ok = true;
break;
}
} while (ok);
return root;
}
int get_cent_dis(int root, int node) const {
auto it = lower_bound(cent_dis[root].begin(), cent_dis[root].end(), make_pair(node, -INF));
if (it == cent_dis[root].end() || it->first != node) return -1;
return it->second;
}
void solve(int root) { // sort函数根据需要修改
root = centroid(root);
for (int u : nodes) if (u != root)
cent_pa[u] = root;
dfs(root); // dfs(root) 计算整颗树的答案，计算某个节点的子树可以使用 dfs(u)
for (int u: nodes)
cent_dis[root].emplace_back(u, dep[u]);
sort(cent_dis[root].begin(), cent_dis[root].end());
for (edge &e : g[root]) {
erase_edge(e.first, root);
}
for (edge &e : g[root])
solve(e.first);
}
template<typename F>
void set(int u, F &&f) { // 更新节点u
for (int x = u; x >= 0; x = cent_pa[x]) {
f(x);
}
}
template<typename F>
void get(int u, F &&f) { // 查询节点u的答案
for (int x = u; x >= 0; x = cent_pa[x]) {
f(x);
}
}
};
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int N, M;
cin >> N >> M;
TreeCD<int> CD(N);
for (int i = 0; i < N - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
CD.add_edge(u, v);
}
CD.solve(0);
vector<int> ans(N,INF);
CD.set(0,[&](int x) {
ans[x] = min(ans[x], CD.get_cent_dis(x, 0));
});
for (int i = 0; i < M; ++i) {
int t, u;
cin >> t >> u;
u--;
if (t==1) {
CD.set(u,[&](int x) {
ans[x] = min(ans[x], CD.get_cent_dis(x, u));
});
} else {
int c = INF;
CD.get(u, [&](int x){
c = min(c, CD.get_cent_dis(x, u) + ans[x]);
});
cout << c << "\n";
}
}
return 0;
}
