Centroid Decomposition
(Graph/centroid.hpp)

• View this file on GitHub
• Last update: 2022-01-05 16:50:26+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;
    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 find(int rt){
        get(rt,-1);
        int res=dfs(rt,-1,rt);
        used[res]=1;
        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;
    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 find(int rt){
        get(rt,-1);
        int res=dfs(rt,-1,rt);
        used[res]=1;
        return res;
    }
};

/**
 * @brief Centroid Decomposition
 */

Back to top page