heavy light decomposition.cpp

#include<bits/stdc++.h>
using namespace std;


///////////////						Heavy Light Decomposition //////////////

#define MAXN 1005

vector<int> g[MAXN], c[MAXN];

int s[MAXN]; // subtree size

int p[MAXN]; // parent id

int r[MAXN]; // chain root id

int t[MAXN]; // index used in segtree/bit/...

int d[MAXN]; // depht

int ts;


void dfs(int v, int f) {

	p[v] = f;

	s[v] = 1;

	if (f != -1) d[v] = d[f] + 1;

	else d[v] = 0;


	for (int i = 0; i < g[v].size(); ++i) {

		int w = g[v][i];

		if (w != f) {

			dfs(w, v);

			s[v] += s[w];

		}

	}

}


void hld(int v, int f, int k) {

	t[v] = ts++;

	c[k].push_back(v);

	r[v] = k;


	int x = 0, y = -1;

	for (int i = 0; i < g[v].size(); ++i) {

		int w = g[v][i];

		if (w != f) {

			if (s[w] > x) {

				x = s[w];

				y = w;

			}

		}

	}

	if (y != -1) {

		hld(y, v, k);

	}


	for (int i = 0; i < g[v].size(); ++i) {

		int w = g[v][i];

		if (w != f && w != y) {

			hld(w, v, w);

		}

	}

}


void init(int n) {

	for (int i = 0; i < n; ++i) {

		g[i].clear();

	}

}


void add(int a, int b) {

	g[a].push_back(b);

	g[b].push_back(a);

}


void build() {

	ts = 0;

	dfs(0, -1);

	hld(0, 0, 0);

}

///////////////						Heavy Light Decomposition //////////////

int main() {

}