Motivation

Given a tree, how many paths of length k are there?

Centroid

  • Claim: We can find a vertex v in tree s.t., none of the subtree has size > N/2 if v is the root of the tree
  • Proof: Suppose we pick a random v as a candidate, if one of its subtree has size > N/2, we move to that subtree’s root.
  • Note that finding the centroid will be similar given the DFS

Centroid decomposition

  1. Starting for the whole tree, find the centroid
  2. find the centroid for each subtree, and connect them to the centroid find in the previous step
  3. recursively apply, until we form a new tree

Properties of Centroid Tree

  1. the new tree contains all nodes of the original tree => by tree induction
  2. The height of the tree is O(logN) => because at each level, the size of max subtree is reduced by at least half
  3. The construction of the tree takes O(nlogn). Because at each level, we traverse each node in the tree at most once, and there are O(logN) levels
  4. Consider any path A - B in the original tree, the path can be broken down to A - C - B where C is the LCA of A and B.

Proof: Both A and B lie in the subtree where C is the original subtree, and they were separated into different subtrees when C is chosen, i.e., C will be node with smallest label in the original A -B path

  1. So we decompose the given tree into O(nlogn) different paths, each of which is a centroid to all its children. Again, the total # is O(nlogn) is because at each level , we introduce O(n) paths, and there are O(logN) levels in total