#include "graph_tree/centroid_decomposition.hpp"
#pragma once #include<vector> #include"graph_template.hpp" /** * @brief 重心分解 */ class centroid_decomposition{ graph g; std::vector<int>used; std::vector<int>v; graph ch; int s; int dfs(int n,int p,int sz,int root){ if(used[n])return 0; bool b=1; int res=1; for(auto e:g[n]){ if(p==e)continue; auto t=dfs(e,n,sz,root); res+=t; if(t>sz/2)b=0; } if(!b||sz-res>sz/2)return res; if(root!=-1)ch[root].push_back(n); else s=n; v.push_back(n); used[n]=1; for(auto e:g[n]){ dfs(e,n,dfs(e,n,g.size()*2,n),n); } return g.size()*2; } public: centroid_decomposition(const graph&g):g(g){ int n=g.size(); used.resize(n); ch.resize(n); dfs(0,-1,n,-1); } int get_root(){return s;} std::vector<int> operator[](int i){return ch[i];} std::vector<int> get_euler_tour(){return v;} };
#line 2 "graph_tree/centroid_decomposition.hpp" #include<vector> #line 3 "graph_tree/graph_template.hpp" #include<tuple> #include<iostream> /** * @brief グラフテンプレート */ using graph=std::vector<std::vector<int>>; template<typename T> using graph_w=std::vector<std::vector<std::pair<int,T>>>; graph load_graph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_digraph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);}return g;} graph load_graph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_digraph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);}return g;} graph load_tree(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_tree0(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;} graph load_treep(int n){graph g(n);for(int i=0;i<n-1;++i){int t;std::cin>>t;g[i+1].push_back(t);g[t].push_back(i+1);}return g;} template<typename T>graph_w<T> load_graph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_digraph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);}return g;} template<typename T>graph_w<T> load_graph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_digraph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);}return g;} template<typename T>graph_w<T> load_tree_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_tree0_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;} template<typename T>graph_w<T> load_treep_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int t;T u;std::cin>>t>>u;g[i+1].emplace_back(t,u);g[t].emplace_back(i+1,u);}return g;} #line 4 "graph_tree/centroid_decomposition.hpp" /** * @brief 重心分解 */ class centroid_decomposition{ graph g; std::vector<int>used; std::vector<int>v; graph ch; int s; int dfs(int n,int p,int sz,int root){ if(used[n])return 0; bool b=1; int res=1; for(auto e:g[n]){ if(p==e)continue; auto t=dfs(e,n,sz,root); res+=t; if(t>sz/2)b=0; } if(!b||sz-res>sz/2)return res; if(root!=-1)ch[root].push_back(n); else s=n; v.push_back(n); used[n]=1; for(auto e:g[n]){ dfs(e,n,dfs(e,n,g.size()*2,n),n); } return g.size()*2; } public: centroid_decomposition(const graph&g):g(g){ int n=g.size(); used.resize(n); ch.resize(n); dfs(0,-1,n,-1); } int get_root(){return s;} std::vector<int> operator[](int i){return ch[i];} std::vector<int> get_euler_tour(){return v;} };