Skip to content

Tree Centroid

This article introduces the concept and basic properties of the centroid of a tree.

Definition

If after deleting a node \(v\) from tree \(T\), the size of each connected component in the resulting graph \(T\setminus\{v\}\) does not exceed half of the total number of nodes in the original tree, then node \(v\) is called a centroid of the entire tree. The size of the largest connected component obtained after deleting a node is also called the weight of that node. Using this concept, the definition of a centroid can be stated as: a node whose weight does not exceed half of the total number of nodes in the tree.

「Subtree」

This article may involve both unrooted trees and rooted trees, as well as trees obtained by re-rooting a rooted tree at a non-root node. To avoid confusion, this article uses \(T\) to denote an unrooted tree and \(T^{(v)}\) to denote a rooted tree with node \(v\) as the root. The term "subtree" mentioned in this article refers to the tree consisting of a node and all its descendants in a rooted tree. In the rooted tree \(T^{(v)}\), the subtree corresponding to node \(u\) is denoted as \(T^{(v)}_u\). Such a defined subtree naturally includes the entire tree itself. To explicitly exclude the entire tree itself, it will be referred to as a "proper subtree".

The term "subtree" in an unrooted tree usually refers to one of its connected subgraphs. When discussing centroids, some authors use the term "subtree" to specifically refer to a maximal connected subgraph that does not contain a certain node, or to one of the two connected components obtained by deleting a certain edge. It can be easily verified that the sets of "subtrees" defined in these two ways are consistent and do not include the entire tree itself. Since they are not consistent with the set of subtrees in a rooted tree, this article will avoid using the concept of "subtree" for unrooted trees.

In practical centroid finding or certain problem-solving contexts, there is usually a default root of the tree. In this case, among the connected components obtained by deleting a non-root node \(v\), besides the subtrees corresponding to its child nodes, there is also an "upward" subtree. Here, let the parent node of node \(v\) be \(u\); this "upward" subtree is \(T_u^{(v)}\). When referring to such subgraphs, this article will explicitly call it an "upward" subtree. Unless otherwise specified, the subtrees mentioned in this article do not include such "upward" subtrees.

Note that these resulting connected components are also unrooted trees. By deleting the centroid of a tree, the tree will be divided into several trees each at most half the size of the original tree. This property of centroids makes it possible to apply divide-and-conquer ideas to solve problems on trees. This is centroid decomposition, also known as tree centroid decomposition.

Properties

This section discusses the properties of centroids. First, the centroid of a tree has the following equivalent definitions:

Equivalent Definitions

A node \(v\) in tree \(T\) is its centroid if and only if any one of the following holds:

  1. After deleting node \(v\) from the tree, the size of each connected component in the resulting graph \(T\setminus\{v\}\) does not exceed half of the total number of nodes in the original tree.
  2. Among the maximum connected component sizes obtained by deleting any node, the value obtained by deleting node \(v\) is the smallest.
  3. Among the sum of distances from all nodes in the tree to a certain node, the sum of distances to node \(v\) is the smallest.
  1. When the tree is rooted at node \(v\), the size of any proper subtree does not exceed half of the total number of nodes in the original tree.
  2. Among the maximum proper subtree sizes when rooted at any node, the value obtained when rooted at node \(v\) is the smallest.
  3. Among the sum of depths of all nodes when rooted at any node, the sum of depths when rooted at node \(v\) is the smallest.
Proof

First, introduce some notation. The two versions for rooted and unrooted trees are clearly equivalent. Define \(W(x)=\max_{u\sim x}|T_u^{(x)}|\), where \(u\sim x\) means \(u\) and \(x\) are adjacent. Define \(S(x)=\sum_{u\in T}d(u,x)\), where \(d(u,x)\) denotes the distance between nodes \(u\) and \(x\). Then, definition 1 is equivalent to requiring \(W(v)\le |T|/2\), definition 2 is equivalent to requiring \(v\in\arg\min_{x\in T}W(x)\), and definition 3 is equivalent to requiring \(v\in\arg\min_{x\in T}S(x)\). What needs to be proved is that these three conditions are equivalent.

Interpreting \(S(x)\) as the sum of node depths when rooted at \(x\), consider its change when the root changes from node \(v\) to an adjacent node \(u\). Note that after deleting edge \((v,u)\) from the tree, the two resulting connected components are the subtrees \(T_v^{(u)}\) and \(T_u^{(v)}\). Before and after the root change, the depth of each node in subtree \(T_v^{(u)}\) increases by \(1\), and the depth of each node in subtree \(T_u^{(v)}\) decreases by \(1\). Therefore, the change in the depth sum is

\[ \Delta S_{v\to u} = S(u) - S(v) = |T_v^{(u)}| - |T_u^{(v)}| = |T| - 2|T_u^{(v)}|. \]

So, the condition of definition 1 is equivalent to requiring \(\Delta S_{v\to u}\le 0\) for all adjacent nodes \(u\) of \(v\), meaning \(v\) is a local minimum point of \(S(x)\).

Now suppose \(v\) is a (global) minimum point of \(S(x)\) (i.e., definition 3). It must exist and is necessarily a local minimum point. Consider the rooted tree \(T^{(v)}\) with root \(v\). Let \(u\neq v\) be a non-root node, and on the directed path from \(v\) to \(u\), let the node immediately after \(v\) be \(y\) (which could be \(u\) itself), and the node immediately before \(u\) be \(x\) (which could be \(v\) itself). Then, because \(T_u^{(x)}\subseteq T_y^{(v)}\), we have

\[ 2|T_x^{(u)}| = 2|T| - 2|T_u^{(x)}| \ge 2|T| - 2|T_y^{(v)}| \ge |T|. \]

The last step uses the fact that \(v\) is a local minimum point of \(S(x)\). At this point, there are two cases:

  • There exists a node \(u\) such that \(2|T_x^{(u)}|=|T|\) holds. Then, according to the inequality above, we must have \((x,u)=(v,y)\), and \(|T_v^{(u)}|=|T_{u}^{(v)}| = |T|/2\). That is, there can be at most one node \(u\) satisfying the equality, and it must be adjacent to \(v\). For all other nodes \(u'\neq u,v\), there must exist \(x'\sim u'\) such that \(|T_{x'}^{(u')}| > |T|/2\). The set of nodes satisfying condition 1 is \(\{v,u\}\).

    Note that after deleting any node, the sum of the sizes of the resulting connected components is always \(|T|-1\). Therefore, if there is a connected component with size at least \(|T|/2\), it must be the largest connected component. Thus, for this case, \(W(v)=W(u)=|T|/2\), and for all \(u'\neq u,v\), we have \(W(u') > |T|/2\). Therefore, the set of nodes satisfying condition 2 is \(\arg\min W(x) = \{v,u\}\).

    Also, because \(\Delta S_{v\to u} = 0\), we have \(S(v)=S(u)\). Since \(v\) is a minimum point, \(u\) must also be a minimum point. For \(u'\neq u,v\), there exists \(x'\sim u'\) such that \(|T_{x'}^{(u')}| > |T|/2\), which violates the condition for a local minimum point. Therefore, \(u'\) cannot be a minimum point either. Thus, the set of nodes satisfying condition 3 is \(\arg\min S(x) = \{v,u\}\).

  • There is no node \(u\) such that \(2|T_x^{(u)}|=|T|\) holds. Then, for all nodes \(u\neq v\), there exists a node \(x\sim u\) such that \(|T_x^{(u)}| > |T|/2\). Repeating the previous analysis shows that for all nodes \(u\neq v\), we have \(W(u) > |T|/2\), and \(u\) is not a local minimum point of \(S(x)\). Therefore, the only node satisfying condition 1 is \(v\), and \(\arg\min W(x)=\arg\min S(x) = \{v\}\).

In either case, the sets satisfying the three conditions are the same. This proves that the three definitions are equivalent.

In addition to these equivalent definitions, tree centroids have the following common properties:

Properties
  1. If a tree's centroid is not unique, then there are exactly two centroids. These two centroids are adjacent. Moreover, after deleting the edge between them, the tree will split into two connected components of equal size.
  2. Adding or deleting a leaf from a tree will move its centroid by at most one edge.
  3. Connecting two trees with an edge to form a new tree, the centroid of the new tree lies on the path connecting the centroids of the original two trees.
  4. The centroid of a rooted tree must lie on the heavy path containing the root node. The centroid of a tree must be an ancestor of the centroid of the subtree corresponding to the root's heavy child.
Proof

Property 1 can be derived from the proof of the equivalent definitions of centroids.

For property 2, it suffices to consider the case of adding a leaf node. This further divides into two cases:

  • Tree \(T\) has only one centroid \(v\). Let \(x\) be the newly added leaf node, and in the graph \(T\cup\{x\}\setminus\{v\}\) obtained by deleting node \(v\) from the new tree, let the connected component containing \(x\) be \(B\cup\{x\}\). Since \(v\) is the unique centroid of tree \(T\), we have \(2|B| < |T|\), i.e., \(2|B|+1\le |T|\). Consequently,

    \[ 2|B\cup\{x\}| = 2(|B|+1) \le |T| + 1 = |T\cup\{x\}|. \]

    Therefore, \(v\) remains a centroid of the new tree \(T\cup\{x\}\). Even if the new tree's centroid is not unique, it must be an adjacent node of \(v\). Thus, the centroid moves at most one edge.

  • Tree \(T\) has two centroids \(u,v\). In this case, the two connected components \(T_u^{(v)}\) and \(T_v^{(u)}\) obtained by deleting \((u,v)\) are of equal size, both \(|T|/2\). Without loss of generality, assume the newly added leaf node \(x\) is attached to the connected component \(T_v^{(u)}\) containing \(v\). Then, because

    \[ |T_v^{(u)}\cup\{x\}| = |T|/2 + 1 > (|T|+1)/2 = |T\cup\{x\}|/2, \]

    \(u\) is no longer a centroid of the new tree. Conversely, after deleting \(v\), there is still a connected component \(T_u^{(v)}\) of size \(|T|/2\), while the sum of sizes of other connected components is

    \[ |T\cup\{x\}| - 1 - |T_u^{(v)}| = |T|/2 \le |T_u^{(v)}|, \]

    so \(v\) remains a centroid of the new tree. Since the new tree has an odd number of nodes, the centroid must be unique. Therefore, the centroid also moves at most one edge.

Summarizing the analysis of both cases reveals that the centroid of the new tree must lie on the path between the old tree's centroid and the newly added leaf node.

Property 3 can be explained by induction. Suppose when connecting \(T\) and \(T'\), the newly added edge is \((x,y)\), with \(x\in T,y\in T'\). Without loss of generality, assume a centroid of the new tree lies in \(T\). Consider the process starting from tree \(T\) and gradually adding nodes from \(T'\) as leaf nodes. It can be proven by induction that a centroid of the tree always lies on the path connecting the centroid of tree \(T\) and node \(x\). The base case is obvious. Assume the proposition holds up to a certain point, and let the current centroid be \(v\). From the analysis of property 2, the centroid of the new tree must lie on the path connecting the newly added node and the current centroid \(v\). Since it cannot move outside tree \(T\), we only need to consider the common part of the path with tree \(T\), i.e., the path connecting the current centroid \(v\) and node \(x\). By the induction hypothesis, \(v\) lies on the path connecting the centroid of tree \(T\) and node \(x\), so the new centroid must also lie on the path connecting the current centroid \(v\) and node \(x\). By induction, the proposition holds.

Property 4 can be explained by combining with the properties of heavy-light decomposition. Let \(v\) be a centroid of tree \(T\). The proposition is obvious when \(v\) is the root node. Now suppose \(v\) is a non-root node, and \(u\) is its parent. Since \(|T_u^{(v)}| \le |T|/2\), the size of the subtree containing \(v\) is at least \(|T|/2\). However, if the path from \(v\) to the root passes through a light edge, the size of the subtree containing \(v\) would be strictly less than \(|T|/2\), a contradiction. Therefore, \(v\) must lie on the heavy path containing the root. Furthermore, by the definition of heavy paths, the heavy path containing the root in the subtree corresponding to the root's heavy child is part of the heavy path containing the root in the original tree. Also, by property 3, after adding the heavy child and all its light child subtrees to the subtree corresponding to the heavy child, the centroid position will move along the path from the current centroid to the root, so the new centroid must be an ancestor of the old centroid.

Finding Centroids

According to the equivalent definitions of centroids, there are two methods to find all centroids of a tree in \(O(n)\) time, where \(n\) is the size of the tree.

DFS to Compute Subtree Sizes

Compute the size of each subtree via DFS. For each node, record the sizes of all subtrees corresponding to its child nodes, and use the total number of nodes minus the size of the current subtree to obtain the size of the "upward" subtree. Then, the centroid can be found based on the definition.

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int MAXN = 50005;

int n;
// This code assumes node indices start from 1, i.e., i ∈ [1,n]
int siz[MAXN],  // The "size" of this node (total nodes in all subtrees + this node)
    weight[MAXN];  // The "weight" of this node, i.e., the maximum "size" among all subtrees
vector<int> centroids;  // Used to record the tree's centroids (stores node indices)
vector<int> g[MAXN];

void dfs(int cur, int fa) {  // cur represents the current node
  siz[cur] = 1;
  weight[cur] = 0;
  for (int v : g[cur]) {
    if (v != fa) {  // v represents the node this directed edge leads to
      dfs(v, cur);
      siz[cur] += siz[v];
      weight[cur] = max(weight[cur], siz[v]);
    }
  }
  weight[cur] = max(weight[cur], n - siz[cur]);
  if (weight[cur] <= n / 2) {  // Collect according to the definition of tree centroid
    centroids.push_back(cur);
  }
}

void get_centroids() { dfs(1, 0); }

Rerooting DP to Compute Depth Sums

Alternatively, use rerooting DP to compute the sum of depths of all nodes (i.e., the sum of distances to the current root) when different nodes are taken as the root. According to the definition, simply find the node that minimizes this depth sum.

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int N = 50005;

int n, siz[N];
long long dp[N], ans[N];
vector<int> g[N], centroids;

// Calculate the sum of distances from node 1 to all other nodes
void dfs1(int u, int fa) {
  siz[u] = 1;
  dp[u] = 0;
  for (int v : g[u]) {
    if (v == fa) continue;
    dfs1(v, u);
    siz[u] += siz[v];
    dp[u] += dp[v] + siz[v];  // Sum of distances from subtree nodes to u
  }
}

// Use rerooting DP to calculate the sum of distances for all nodes as the tree root
void dfs2(int u, int fa) {
  for (int v : g[u]) {
    if (v == fa) continue;
    ans[v] = ans[u] - siz[v] + (n - siz[v]);
    dfs2(v, u);
  }
}

// Find the centroid(s) of the tree
void get_centroids() {
  dfs1(1, 0);
  ans[1] = dp[1];
  dfs2(1, 0);

  long long mini = std::numeric_limits<long long>::max();
  for (int i = 1; i <= n; i++) {
    if (ans[i] < mini) {
      mini = ans[i];
      centroids = {i};
    } else if (ans[i] == mini)
      centroids.push_back(i);
  }
}

Example Problems

Codeforces Round 359 (Div. 1) B. Kay and Snowflake

Given a rooted tree, find the centroid of each subtree.

Solution Idea

According to property 3, for a subtree rooted at node \(u\), its centroid must lie on the path from the centroids of all subtrees rooted at \(u\)'s direct children to node \(u\).

Similar to the DFS method for finding centroids mentioned above, for each subtree rooted at node \(u\), first find the centroids of all subtrees rooted at its direct children (the centroid of a leaf node is itself), then check upwards along the path to see if nodes on the path are centroids.

All subtree centroids can be found in \(O(n)\) time.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
using namespace std;

constexpr int N = 3e5 + 5;

int n, q;  // Number of nodes, number of queries
int fa[N];
vector<int> son[N];
int siz[N],     // Subtree size
    ans[N],     // The centroid of the subtree rooted at node u is ans[u]
    weight[N];  // Node weight (excluding the upward subtree)

void dfs(int u) {
  siz[u] = 1, ans[u] = u;
  for (int v : son[u]) {
    dfs(v);
    siz[u] += siz[v];
    weight[u] = max(weight[u], siz[v]);
  }
  for (int v : son[u]) {
    int p = ans[v];
    while (p != u) {
      if (max(weight[p], siz[u] - siz[p]) <= siz[u] / 2) {
        ans[u] = p;
        break;
      } else
        p = fa[p];
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> q;
  for (int v = 2; v <= n; v++) cin >> fa[v], son[fa[v]].push_back(v);
  dfs(1);
  while (q--) {
    int u;
    cin >> u;
    cout << ans[u] << '\n';
  }
  return 0;
}

Exercises

References

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用