重心分解クエリ補助(Centroid Query Helper)
(tree/centroid_decomposition_query_helper.cpp)

• View this file on GitHub
• Last update: 2026-03-12 00:49:33+09:00

説明

重心分解の重心木と、各頂点から重心祖先への距離列を前計算する補助。 最近点距離、加点・集約系などの典型クエリで、そのままループを書き始めやすい形にする。

できること

• CentroidDecompositionQueryHelper cd(n) 頂点数 n の木を作る
• void add_edge(int u, int v) 木辺を張る
• int build(int start = 0) 重心分解して重心木の根を返す

使い方

build() 後は tree、parent、depth、path、dist を参照する。

• tree[c] 重心木での子重心
• parent[c] 重心木での親重心。根なら -1
• depth[c] 重心木での深さ
• path[v][i] 頂点 v から見た i 番目の重心祖先。近い順に入る
• dist[v][i] 頂点 v から path[v][i] までの距離

path[v] と dist[v] は同じ長さで、path[v].back() は重心木の根になる。

例

最近点距離クエリは、重心ごとに最良値を持てば書ける。

const int INF = 1e9;
vector<int> best(n, INF);

auto add = [&](int v) {
    for (int i = 0; i < (int)cd.path[v].size(); ++i) {
        best[cd.path[v][i]] = min(best[cd.path[v][i]], cd.dist[v][i]);
    }
};

auto query = [&](int v) {
    int ans = INF;
    for (int i = 0; i < (int)cd.path[v].size(); ++i) {
        ans = min(ans, best[cd.path[v][i]] + cd.dist[v][i]);
    }
    return ans;
};

Code

using namespace std;

struct CentroidDecompositionQueryHelper {
    int n, root;
    vector<vector<int>> G, tree, path, dist;
    vector<int> sz, parent, depth;
    vector<char> used;

    explicit CentroidDecompositionQueryHelper(int n)
        : n(n), root(-1), G(n), tree(n), path(n), dist(n), sz(n), parent(n, -1), depth(n), used(n, 0) {}

    void add_edge(int u, int v) {
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int build(int start = 0) {
        tree.assign(n, {});
        path.assign(n, {});
        dist.assign(n, {});
        fill(parent.begin(), parent.end(), -1);
        fill(depth.begin(), depth.end(), 0);
        fill(used.begin(), used.end(), 0);
        if (n == 0) return root = -1;
        return root = decompose(start, -1, 0);
    }

private:
    int dfs_size(int v, int p) {
        sz[v] = 1;
        for (auto &&u : G[v]) {
            if (u == p || used[u]) continue;
            sz[v] += dfs_size(u, v);
        }
        return sz[v];
    }

    int find_centroid(int v, int p, int half) {
        for (auto &&u : G[v]) {
            if (u == p || used[u]) continue;
            if (sz[u] > half) return find_centroid(u, v, half);
        }
        return v;
    }

    void collect(int v, int p, int d, vector<pair<int, int>> &buf) {
        buf.emplace_back(v, d);
        for (auto &&u : G[v]) {
            if (u == p || used[u]) continue;
            collect(u, v, d + 1, buf);
        }
    }

    int decompose(int start, int p, int dep) {
        int centroid = find_centroid(start, -1, dfs_size(start, -1) / 2);
        used[centroid] = 1;
        parent[centroid] = p;
        depth[centroid] = dep;
        path[centroid].push_back(centroid);
        dist[centroid].push_back(0);
        for (auto &&u : G[centroid]) {
            if (used[u]) continue;
            vector<pair<int, int>> buf;
            collect(u, centroid, 1, buf);
            int child = decompose(u, centroid, dep + 1);
            tree[centroid].push_back(child);
            for (auto &&[v, d] : buf) {
                path[v].push_back(centroid);
                dist[v].push_back(d);
            }
        }
        return centroid;
    }
};

/**
 * @brief 重心分解クエリ補助(Centroid Query Helper)
 */

#line 1 "tree/centroid_decomposition_query_helper.cpp"
using namespace std;

struct CentroidDecompositionQueryHelper {
    int n, root;
    vector<vector<int>> G, tree, path, dist;
    vector<int> sz, parent, depth;
    vector<char> used;

    explicit CentroidDecompositionQueryHelper(int n)
        : n(n), root(-1), G(n), tree(n), path(n), dist(n), sz(n), parent(n, -1), depth(n), used(n, 0) {}

    void add_edge(int u, int v) {
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int build(int start = 0) {
        tree.assign(n, {});
        path.assign(n, {});
        dist.assign(n, {});
        fill(parent.begin(), parent.end(), -1);
        fill(depth.begin(), depth.end(), 0);
        fill(used.begin(), used.end(), 0);
        if (n == 0) return root = -1;
        return root = decompose(start, -1, 0);
    }

private:
    int dfs_size(int v, int p) {
        sz[v] = 1;
        for (auto &&u : G[v]) {
            if (u == p || used[u]) continue;
            sz[v] += dfs_size(u, v);
        }
        return sz[v];
    }

    int find_centroid(int v, int p, int half) {
        for (auto &&u : G[v]) {
            if (u == p || used[u]) continue;
            if (sz[u] > half) return find_centroid(u, v, half);
        }
        return v;
    }

    void collect(int v, int p, int d, vector<pair<int, int>> &buf) {
        buf.emplace_back(v, d);
        for (auto &&u : G[v]) {
            if (u == p || used[u]) continue;
            collect(u, v, d + 1, buf);
        }
    }

    int decompose(int start, int p, int dep) {
        int centroid = find_centroid(start, -1, dfs_size(start, -1) / 2);
        used[centroid] = 1;
        parent[centroid] = p;
        depth[centroid] = dep;
        path[centroid].push_back(centroid);
        dist[centroid].push_back(0);
        for (auto &&u : G[centroid]) {
            if (used[u]) continue;
            vector<pair<int, int>> buf;
            collect(u, centroid, 1, buf);
            int child = decompose(u, centroid, dep + 1);
            tree[centroid].push_back(child);
            for (auto &&[v, d] : buf) {
                path[v].push_back(centroid);
                dist[v].push_back(d);
            }
        }
        return centroid;
    }
};

/**
 * @brief 重心分解クエリ補助(Centroid Query Helper)
 */

Back to top page