library/tree/CentroidDecomposition.hpp

• View this file on GitHub
• Last update: 2025-10-31 18:20:20+09:00
• Include: #include "library/tree/CentroidDecomposition.hpp"

Depends on

• library/template/template.hpp

Verified with

• verify/yosupo/frequency-tree-distance.test.cpp

Code

#pragma once

#include "../template/template.hpp"
template <class G>
struct CentroidDecomposition {
	const G &g;
	vl sub;
	vec<bool> v;
	vv<ll> tree;
	ll root;

	CentroidDecomposition(const G &g_, bool isbuild = true) : g(g_) {
		sub.resize(sz(g), 0ll);
		v.resize(sz(g), false);
		if (isbuild) build();
	}
	void build() {
		tree.resize(sz(g));
		root = build_dfs(0);
	}
	ll get_size(ll cur, ll par) {
		sub[cur] = 1;
		for (auto &dst : g[cur]) {
			if (dst == par || v[dst]) continue;
			sub[cur] += get_size(dst, cur);
		}
		return sub[cur];
	}
	ll get_centroid(ll cur, ll par, ll mid) {
		for (auto &dst : g[cur]) {
			if (dst == par || v[dst]) continue;
			if (sub[dst] > mid) return get_centroid(dst, cur, mid);
		}
		return cur;
	}
	ll build_dfs(ll cur) {
		ll centroid = get_centroid(cur, -1, get_size(cur, -1) / 2);
		v[centroid] = true;
		for (auto &dst : g[centroid]) {
			if (!v[dst]) {
				ll nxt = build_dfs(dst);
				if (centroid != nxt) tree[centroid].emplace_back(nxt);
			}
		}
		v[centroid] = false;
		return centroid;
	}
};

#line 2 "library/tree/CentroidDecomposition.hpp"

#line 2 "library/template/template.hpp"

#include <bits/stdc++.h>
using namespace std;
#define MM << ' ' <<
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, r) for(ll i = 0; i < (r); i++)
#define reps(i, l, r) for(ll i = (l); i < (r); i++)
#define rrep(i, l, r) for(ll i = (r) - 1; i >= l; i--)
template <class T> void uniq(T &a) { sort(all(a)); erase(unique(all(a)), a.end()); }
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)(a).size()
const ll INF = numeric_limits<ll>::max() / 4;
const ld inf = numeric_limits<ld>::max() / 2;
const ll mod1 = 1000000007;
const ll mod2 = 998244353;
const ld pi = 3.141592653589793238;
template <class T> void rev(T &a) { reverse(all(a)); }
ll popcnt(ll a) { return __builtin_popcountll(a); }
template<typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template<typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	os << p.first << " " << p.second;
	return os;
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
	is >> p.first >> p.second;
	return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vec<T>& v) {
	rep(i, sz(v)) {
		os << v[i] << " \n"[i + 1 == sz(v)];
	}
	return os;
}
template <typename T>
istream& operator>>(istream& is, vec<T>& v) {
	for (T& in : v) is >> in;
	return is;
}
void yesno(bool t) {
	cout << (t ? "Yes" : "No") << endl;
}
#line 4 "library/tree/CentroidDecomposition.hpp"
template <class G>
struct CentroidDecomposition {
	const G &g;
	vl sub;
	vec<bool> v;
	vv<ll> tree;
	ll root;

	CentroidDecomposition(const G &g_, bool isbuild = true) : g(g_) {
		sub.resize(sz(g), 0ll);
		v.resize(sz(g), false);
		if (isbuild) build();
	}
	void build() {
		tree.resize(sz(g));
		root = build_dfs(0);
	}
	ll get_size(ll cur, ll par) {
		sub[cur] = 1;
		for (auto &dst : g[cur]) {
			if (dst == par || v[dst]) continue;
			sub[cur] += get_size(dst, cur);
		}
		return sub[cur];
	}
	ll get_centroid(ll cur, ll par, ll mid) {
		for (auto &dst : g[cur]) {
			if (dst == par || v[dst]) continue;
			if (sub[dst] > mid) return get_centroid(dst, cur, mid);
		}
		return cur;
	}
	ll build_dfs(ll cur) {
		ll centroid = get_centroid(cur, -1, get_size(cur, -1) / 2);
		v[centroid] = true;
		for (auto &dst : g[centroid]) {
			if (!v[dst]) {
				ll nxt = build_dfs(dst);
				if (centroid != nxt) tree[centroid].emplace_back(nxt);
			}
		}
		v[centroid] = false;
		return centroid;
	}
};

Back to top page