XCPC wiki - 树 04 - 树的重心剖分、点分治

树的重心

1. 树的重心要么 惟一，要么 有两个，且这两个重心相邻。
2. 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半，即 siz[v] * 2 < siz[u]。
3. 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
4. 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
5. 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

求树的重心

vector<int> siz(n), mss(n);  // 固定根时的子树大小 最大子树大小
auto dfs = [&](this auto&& dfs, int u, int p) -> void {
    siz[u] = 1;
    for (auto v : E[u]) {
        if (v == p) continue;
        dfs(v, u);
        siz[u] += siz[v];
        mss[u] = max(mss[u], siz[v]);
    }
};
dfs(s, -1);

vector<int> ctrs;
for (int u = 0; u < n; u++) {
    mss[u] = max(mss[u], siz[s] - siz[u]);
    if (siz[u] && mss[u] <= siz[s] / 2) ctrs.push_back(u);
}

求有根树的所有子树的重心

利用性质 4。

int n;
vector<int> E[N];
int p[N];
int siz[N];        // 固定根时的子树大小
int hson[N];       // 重儿子
int ctr[N];
 
void dfs(int u, int p = 0) {
    siz[u] = 1;
    p[u] = p;
    hson[u] = 0;
    for (auto& v : E[u]) {
        if (v == p) continue;
        dfs(v, u);
        siz[u] += siz[v];
        if (siz[hson[u]] < siz[v]) hson[u] = v;
    }

    if (siz[hson[u]] * 2 >= siz[u]) {
        int v = ctr[hson[u]];
        while (siz[v] * 2 <= siz[u]) v = p[v];
        ctr[u] = v;
    }
    else {
        ctr[u] = u;
    }
}

void eachT() {
    n = read();
    for (int i = 2; i <= n; i++) {
        int u = read(), v = read();
        E[u].push_back(v), E[v].push_back(u);
    }
    dfs(1);
    for (int u = 1; u <= n; u++) printf("%d\n", ctr[u]);
}

2024 ICPC 南京 G. Binary Tree

给定一棵二叉树，找隐藏的特殊节点，每次询问$x,y$，返回这两者到特殊节点的距离大小关系，至多$\lfloor \log_{2}n \rfloor$ 次。数据范围：$n \leqslant 10^{5}$。

思路 问直径是不行的，每问$\log_{2}k$ 次可以砍掉$k$ 个节点，$n=\sum k$，则$\sum\log_{2}k=\log_{2}\prod k>\log_{2}\sum k=\log_{2}n$，次数超了。

希望每次询问砍掉 至少一半 的节点，考虑问重心，类似点分治的想法。

每个点至多有三个相邻节点$x,y,z$，按称假砝码的思路，问其中两个节点$x,y$，若$d_{x}>d_{y}$ 则在$y$ 那边，若$d_{x}<d_{y}$ 则在$x$ 那边，若$d_{x}=d_{y}$ 则在$z$ 那边，或者是重心自己。

问题出在至少一半和或者是重心自己，如果总共$5$ 个节点，且$s_{x}=1,s_{y}=1,s_{z}=2$，且问到$d_{x}=d_{y}$，那么剩下的是$z$ 那边的子树或重心自己，剩下了$3$ 个节点，这是不行的。所以问其中两个节点$x,y$ 不是任意选的，应当问子树大小较大的两个。

这样每次询问一定能砍掉至少一半的节点。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;

		int _cnt = 0, _max = __lg(n);
		auto query = [&](int x, int y) {
			assert(++_cnt <= _max);
			cout << "? " << ++x << " " << ++y << endl;
			cin >> x;
			return x;
		};
		
		auto answer = [&](int x) {
			cout << "! " << ++x << endl;
		};

		vector<vector<int>> E(n);

		for (int i = 0; i < n; i++) {
			int l, r;
			cin >> l >> r;
			l--, r--;
			if (l != -1) E[i].push_back(l), E[l].push_back(i);
			if (r != -1) E[i].push_back(r), E[r].push_back(i);
		}

		int s = 0;
		while (1) {
			vector<int> siz(n), mss(n);
			auto dfs = [&](auto&& dfs, int u, int p) -> void {
				siz[u] = 1;
				for (auto v : E[u]) {
					if (v == p) continue;
					dfs(dfs, v, u);
					siz[u] += siz[v];
					mss[u] = max(mss[u], siz[v]);
				}
			};
			dfs(dfs, s, -1);

			int ctr;
			int tot = siz[s];
			for (int u = 0; u < n; u++) {
				mss[u] = max(mss[u], tot - siz[u]);
				if (siz[u] && mss[u] <= tot / 2) ctr = u;
			}

			if (E[ctr].empty()) {
				answer(ctr);
				break;
			} else if (E[ctr].size() == 1) {
				int u = ctr, v = E[ctr][0];
				int x = query(u, v);
				if (x == 0) {  // d(u) < d(v)
					answer(u);
					break;
				} else {  // d(u) > d(v)
					answer(v);
					break;
				}
			} else {
				sort(E[ctr].begin(), E[ctr].end(), [&](const int u, const int v) {
					return mss[u] < mss[v];
				});

				int u = E[ctr][0], v = E[ctr][1];
				int x = query(u, v);
				if (x == 0) {  // d(u) < d(v)
					s = u;
					E[s].erase(find(E[s].begin(), E[s].end(), ctr));
				} else if (x == 2) {  // d(u) > d(v)
					s = v;
					E[s].erase(find(E[s].begin(), E[s].end(), ctr));
				} else {  // d(u) == d(v)
					s = ctr;
					E[s].erase(E[s].begin());
					E[s].erase(E[s].begin());
				}
			}
		}
	}

	return 0;
}

点分治

点分治 或 重心剖分 (Centroid Decomposition) 是树分治的一种，处理 树上点对/路径问题。

为遍历树上所有的路径，利用分治思想：对于每个点，我们分别考虑包含这个点的路径和不包含这个点的路径。对于前者，做一趟 DFS；对于后者，删除该点后，对所有子树递归地处理。

每次选择子树的重心作为子树的根，那么复杂度可以保证为 $\Theta(n\log n)$。因为按照这种选法，每个递归问题中子树的大小都不超过整棵树的一半，所以每次递归问题规模可以下降至一半或更低。

处理树上点对/路径、期望复杂度$\Theta(n\log n)$ 且单次询问的问题，可考虑点分治。只需考虑如何在$\Theta(n)$ 时间求出 以根为 lca 的点对，即 包含根的路径 的答案。

struct TDC {
    int n;
    int ctr;                // 分治树的重心
    int ttsiz;              // 分治树的大小
    vector<int> mss;        // 分治树的最大子树大小 找重心时用 
    vector<int> siz;        // 子树大小
    vector<int> vis;        // 是否分治过
    vector<vector<pair<int, int>>> E;

    TDC(int n) : n(n), ctr(0), ttsiz(0), mss(n), siz(n), vis(n), E(n) {
        siz[0] = n;
    }

    void add(int u, int v, int w) {
        E[u].push_back({ w, v });
        E[v].push_back({ w, u });
    }

    // 找重心 
    void get_ctr(int u, int p = 0) {
        siz[u] = 1, mss[u] = 0;
        for (auto& [w, v] : E[u]) {
            if (v == p || vis[v]) continue;
            get_ctr(v, u);
            siz[u] += siz[v];
            mss[u] = max(mss[u], siz[v]);
        }
        mss[u] = max(mss[u], ttsiz - siz[u]);
        if (mss[u] < mss[ctr]) ctr = u;
    }

    void cal(int u);

    // 点分治 u为重心
    void devide(int u) {
        vis[u] = true;
        cal(u);
        for (auto& [w, v] : E[u]) {
            if (vis[v]) continue;
            solve(v);
        }
    }

    void solve(int u = 0) {
        ctr = 0, mss[ctr] = n, ttsiz = siz[u];
        get_ctr(u);
        devide(ctr);
    }
};

void TDC::cal(int u) {
    // ...
}

int main() {
    int n;
    cin >> n;
    TDC G(n);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G.add(u, v, w);
    }
    G.solve();
    return 0;
}