library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Centroid Decomposition
(Graph/centroid.hpp)

• View this file on GitHub
• Last update: 2024-11-30 06:30:49+09:00
• Include: #include "Graph/centroid.hpp"

Required by

• Contour Sum Query (Graph/contour.hpp)

Verified with

• Verify/LC_frequency_table_of_tree_distance.test.cpp
• Verify/LC_vertex_add_range_contour_sum_on_tree.test.cpp

Code

#pragma once

class CentroidDecomposition {
    void get(int v, int p) {
        sz[v] = 1;
        for (auto &to : g[v])
            if (to != p and !used[to]) {
                get(to, v);
                sz[v] += sz[to];
            }
    }
    int dfs(int v, int p, int rt) {
        for (auto &to : g[v])
            if (to != p and !used[to]) {
                if (sz[to] > (sz[rt] >> 1))
                    return dfs(to, v, rt);
            }
        return v;
    }

  public:
    int n, all;
    vector<vector<int>> g;
    vector<int> sz, used;
    CentroidDecomposition(int n_) : n(n_), g(n), sz(n), used(n) {}
    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int size(int rt) {
        get(rt, -1);
        return sz[rt];
    }
    int find(int rt) {
        get(rt, -1);
        all = sz[rt];
        int res = dfs(rt, -1, rt);
        return res;
    }
};

/**
 * @brief Centroid Decomposition
 */

#line 2 "Graph/centroid.hpp"

class CentroidDecomposition {
    void get(int v, int p) {
        sz[v] = 1;
        for (auto &to : g[v])
            if (to != p and !used[to]) {
                get(to, v);
                sz[v] += sz[to];
            }
    }
    int dfs(int v, int p, int rt) {
        for (auto &to : g[v])
            if (to != p and !used[to]) {
                if (sz[to] > (sz[rt] >> 1))
                    return dfs(to, v, rt);
            }
        return v;
    }

  public:
    int n, all;
    vector<vector<int>> g;
    vector<int> sz, used;
    CentroidDecomposition(int n_) : n(n_), g(n), sz(n), used(n) {}
    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int size(int rt) {
        get(rt, -1);
        return sz[rt];
    }
    int find(int rt) {
        get(rt, -1);
        all = sz[rt];
        int res = dfs(rt, -1, rt);
        return res;
    }
};

/**
 * @brief Centroid Decomposition
 */

Back to top page