Decompositions

pre-requisites

the idea of such decomposition algorithms on trees is that any “breaking” you do, for a reference pair of nodes (u,v) they will be in ONE component until some specific node c, splits them into different ones. What we “do” with the decomposition as in what algorithms we apply on the decomposed tree would work on ANY decomposition really — even the original tree; what does change is the time complexity due to structure created by the decomp

There can be many decompositions of a tree like lca decomposition, centroid decomp, heavy-light decomp etc. The problem in focus in this page is distance queries since there are SO MANY ways to do it; the lca one is standard of course but the point is to learn.

lca decomposition

the idea is the break paths u→v to u→lca and lca→v what is special about the lca here? it decomposes the dfs direction reversal into two parts cleanly so you can use information stored between those nodes and account for that direction change in computations

for example in distance queries, it breaks it into sum of two level diffs as up then down breaks into down and down

this is the core function

auto dist = [&](int u, int v) -> int {
    // say h(u) >= h(v) then two cases
    // lca(u,v) is v in which case ans is just a level diff(u,v)
    // = l(u) - l(v)
    // OR
    // lca(u,v) = a ( some diff node ) then it's simply
    // level diff(u,a) + level diff(v,a)
    // = l(u) - l(a) + l(v) - l(a)
    // notice that when a = v, this too collapse to first case
    // so can just use result from case 2
    return h[u] + h[v] - 2 * h[lca(u, v)];
};

centroid decomposition

centroid = for n node tree, node which when removed breaks each component into floor(n/2) sized components. It cannot be ceil EVER since you already are at n-1 nodes remaining so it floor you down wrt to the original n.

now notice that this ENSURES that we are going to subproblems that are AT LEAST half of original ( this isn’t guaranteed if you start working directly on the original tree )

in essence, centroid decomposition is a “separator” trick ( any such decomposition is just that really )

say c is the centroid of the original tree, removing that we get blobs like A, B, C… the way c becomes useful is that we KNOW that any u in A, and for any v in B or C, the PATH must PASS through c.

another key point is that the whole idea of a decomp is to highlight USEFUL nodes in the path, like lca or centroid in this case so you can split the computation about those USEFUL nodes and do them as sum of parts. All sizes, distances etc are ever only used for the original tree and the “numbers” of the centroid tree are not at ALL relevant, only what nodes it reveals as useful on the original tree.

implementation

vector<int> sz(n + 1), cd_par(n + 1), cd_depth(n + 1), removed(n + 1);
vector<vector<int>> cd(n + 1); // optional, centroid tree
vector<vector<int>> dist_to_cd(n + 1);
 
auto getsz = [&](auto &&f, int u, int p) -> int {
	sz[u] = 1;
	for (int v : g[u])
		if (v != p && !removed[v])
			sz[u] += f(f, v, u);
	return sz[u];
};
 
auto getcentroid = [&](auto &&f, int u, int p, int tot) -> int {
	for (int v : g[u])
		if (v != p && !removed[v] && sz[v] > tot / 2)
			return f(f, v, u, tot);
	return u;
};
 
auto filldist = [&](auto &&f, int u, int p, int d) -> void {
	dist_to_cd[u].push_back(d); // dist_to_cd[u][cd_depth[c]] = dist(u, c)
	for (int v : g[u])
		if (v != p && !removed[v])
			f(f, v, u, d + 1);
};
 
auto build_cd = [&](auto &&f, int entry, int p) -> void {
	int tot = getsz(getsz, entry, 0);
	int c = getcentroid(getcentroid, entry, 0, tot);
 
	cd_par[c] = p;          // 0 means centroid-root
	cd_depth[c] = p ? cd_depth[p] + 1 : 0;
	filldist(filldist, c, 0, 0);
	removed[c] = 1;
 
	if (p)
		cd[p].push_back(c); // optional
 
	for (int v : g[c])
		if (!removed[v])
			f(f, v, c);
};
 
build_cd(build_cd, 1, 0);

The code is for reference, here’s the chain of thought

• as I remove nodes from the tree, I need t mark them removed, and these removals invalidate ANY sizes or dfs precomputions I could’ve done so I need to do them on the fly AND have them account for removed
• this above gets you to a TRIVIAL imp of getsz
• getcentroid is trivial too. What you do is that you ASSUME the current node is centroid and do a usual dfs BUT wherever you find a component larger than n/2 that centroid MUTS be in that comp. If no such case, current nodes IS the centroid.
• Now note that you don’t NEED to get sizes each time for a centroid level, so the way it’s done is you do getsz to POPULATE a size array, that is meant to be used only while it’s not STALE due to a removal ( so within the current component’s centroid finding is it’s lifetime )
• now NOTE that here we don’t have height related information at all, unlike lca. In most such decomps what you do is travel up/down ALONG the path in the centroid tree ( note that this will be log n )
• also NOTE that filldist has fills distances AS THEY ARE in the original tree.
• ESSENCE: as you move from up from one centroid to another, you move along “pitstops” on the path where you know the compuations as they are on the original subtree for in between those pitstops.
• now with all of the above in mind, build_cd is really as simple as the code itself.

example: tree distances

to note; because I had this misconception. The first common node going up in centroid tree is NOT necessarily the lca in the original tree

the core idea is that you buld centroid tree, then for a pair (u,v), you can go up to the top of the centroid tree and keep on marking nodes. Then do the same from v, except as soon as you high a marked node → this implies this node is on the path between u to v

implementation: tree distances

ramp trick gem say I want a visited array but 0/1 and for it be re-used I would need to clear it. Idea is to say keep a counter, and whenever you want to clear it, you update the counter. To mark seen, set the value as counter; any value < counter is just 0.

// problem: fast (u,v) distance queries
// tag: centroid decomp
 
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	// finally needed to put these in for this problem
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
 
#define int long long
	int n, q;
	cin >> n >> q;
	vector<vector<int>> g(n + 1);
 
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
 
	vector<int> sz(n + 1), removed(n + 1), cd_par(n + 1), cd_depth(n + 1);
	// centroid_dist ( not cd_dist as it's not centroid decomposition dist )
	vector<vector<int>> c_dist(n + 1);
 
	auto fsz = [&](auto &&f, int u, int par) -> int {
		sz[u] = 1;
		for (int v : g[u]) {
			if (v == par || removed[v])
				continue;
			sz[u] += f(f, v, u);
		}
		return sz[u];
	};
 
	auto fcentroid = [&](auto &&f, int u, int par, int tot) -> int {
		for (int v : g[u]) {
			if (v == par || removed[v])
				continue;
			if (sz[v] > tot / 2)
				return f(f, v, u, tot);
		}
		return u;
	};
 
	auto fdist = [&](auto &&f, int u, int par, int d) -> void {
		// for each node in the component with the centroid, centroid
		// starts as root and we fill in a dist
		// note that for same node, this dfs will never push twice
		c_dist[u].push_back(d);
		for (int v : g[u]) {
			if (v == par || removed[v])
				continue;
			f(f, v, u, d + 1);
		}
	};
 
	auto fcd = [&](auto &&f, int u, int par) -> void {
		// note that par IS 0 as these are just individual trees and
		// meant to be treated as such
		int tot = fsz(fsz, u, 0);
		int c = fcentroid(fcentroid, u, 0, tot);
 
		// USE the centroid to fill info, note that you CANNOT remove
		// it yet
		fdist(fdist, c, 0, 0);
		if (par) {
			cd_depth[c] = cd_depth[par] + 1;
			cd_par[c] = par;
		}
 
		// now remove
		removed[c] = 1;
 
		for (int v : g[c]) {
			// this v == par is redundant as parent must be SOME centroid
			// and MUST have been removed in the prev iteration
			if (v == par || removed[v])
				continue;
			f(f, v, c);
		}
	};
	fcd(fcd, 1, 0);
 
	vector<int> seen(n + 1);
	int ctr = 0;
	auto dist = [&](int u, int v) -> int {
		// the idea is that you do ramp trick here for seen
		// and find the lowest centroid ancestor ( cca )
		// ^ is the centroid that split it into two components ( so u,v split to
		// siblinds trees now ). so if you decompose the path alon that, and you
		// have distances in both, you can sum them up
 
		++ctr;
		for (int x = u; x; x = cd_par[x]) {
			seen[x] = ctr;
		}
 
		// from v go up till you hit seen
		for (int x = v; x; x = cd_par[x]) {
			if (seen[x] == ctr) {
				// hit a seen
				// note that for the cd tree, root is the first elem in cd dist
				// then for the node, next is dist to whatever is NEXT centroid
				// in the child tree and so on, so dist(u) => {c0, c1, c2...}
				// where ci is the ith node as you move from root to the current
				// node IN the cd tree. to summarise for each original node u,
				// dist_to_cd[u] stores distances to the centroid ancestors of
				// u, ordered by centroid depth:
				//
				// now ^ isn't self evident, after all, the depth DOES not
				// depent on u, where we started from, even though we are
				// checking u's dist array. Depth in cd tree would be the entry
				// in cd_dist(u). This is not obvious why -- but it's due to the
				// fill
				//
				// this of it as, x MUST be a a centroid ancestor, that is by
				// contruction here if this is then at dep 2 in the cd tree,
				// then at dep 1, and at dep 0, we also had a centroid ancestor,
				// and they TOO must've pushed a dist value corresponding to
				// them so this cd_depth is VERY much rooted into x being an
				// ancestor in cd tree
				int ans = c_dist[u][cd_depth[x]] + c_dist[v][cd_depth[x]];
				return ans;
			}
		}
 
		return -1ll;
	};
 
	while (q--) {
		int u, v;
		cin >> u >> v;
		cout << dist(u, v) << "\n";
	}
 
#undef int
}

What I did wrong initially

• incorrectly using “u” as node where I should’ve used “c”
• being a bit confused as to IF I pass in 0 or par to the individual functions ( it’s 0, they are their own separate trees in the subproblem )