Tree Center

Definition

In a tree, if node \(x\) as the root yields the shortest longest chain starting from \(x\), then \(x\) is called the center of the tree.

Properties

The center of a tree is not necessarily unique, but there are at most 2 centers, and these two centers are adjacent.
The center of a tree must lie on the tree's diameter.
The paths from all nodes in the tree to their farthest points must intersect at the tree's center.
When the tree's center is taken as the root, the two chains reaching the endpoints of the diameter are the longest chain and the second longest chain, respectively.
When merging two trees into one by adding an edge between them, connecting the centers of the two trees minimizes the diameter of the new tree.
The distance from the tree's center to any other node does not exceed half of the tree's diameter.

Finding the Center

Find a node \(x\) such that when \(x\) is taken as the root, the length of the longest chain is minimized.

Detailed Steps

Maintain \(len1_x\), representing the longest chain within the subtree of node \(x\).
Maintain \(len2_x\), representing the longest chain that does not overlap with \(len1_x\).
Maintain \(up_x\), representing the longest chain outside the subtree of node \(x\), which must pass through the parent of \(x\).
Find the node \(x\) that minimizes \(\max(len1_x, up_x)\). Then \(x\) is the center of the tree.

Reference Code

// This code assumes node indices start from 1, i.e., i ∈ [1,n], and uses vector for graph storage.
int d1[N], d2[N], up[N], x, y, mini = 1e9;  // d1, d2 correspond to len1, len2 above

struct node {
  int to, val;  // to is the node the edge points to, val is the edge weight
};

vector<node> nbr[N];

void dfsd(int cur, int fa) {  // Compute len1 and len2
  for (node nxtn : nbr[cur]) {
    int nxt = nxtn.to, w = nxtn.val;  // nxt is the node reached by this edge, val is the edge weight
    if (nxt == fa) {
      continue;
    }
    dfsd(nxt, cur);
    if (d1[nxt] + w > d1[cur]) {  // Can update the longest chain
      d2[cur] = d1[cur];
      d1[cur] = d1[nxt] + w;
    } else if (d1[nxt] + w > d2[cur]) {  // Cannot update the longest chain, but can update the second longest chain
      d2[cur] = d1[nxt] + w;
    }
  }
}

void dfsu(int cur, int fa) {
  for (node nxtn : nbr[cur]) {
    int nxt = nxtn.to, w = nxtn.val;
    if (nxt == fa) {
      continue;
    }
    up[nxt] = up[cur] + w;
    if (d1[nxt] + w != d1[cur]) {  // If the longest chain in the current subtree is not in the nxt subtree
      up[nxt] = max(up[nxt], d1[cur] + w);
    } else {  // The longest chain in the current subtree is in the nxt subtree, must use the second longest chain
      up[nxt] = max(up[nxt], d2[cur] + w);
    }
    dfsu(nxt, cur);
  }
}

void GetTreeCenter() {  // Compute the tree center(s), stored as x and y (if exists)
  dfsd(1, 0);
  dfsu(1, 0);
  for (int i = 1; i <= n; i++) {
    if (max(d1[i], up[i]) < mini) {  // Found the node with the current minimum max(len1[x], up[x])
      mini = max(d1[i], up[i]);
      x = i;
      y = 0;
    } else if (max(d1[i], up[i]) == mini) {  // Another center
      y = i;
    }
  }
}

Example

Suppose we have a tree as follows:

The diameter of the tree is \(D \rightarrow B \rightarrow A \rightarrow C \rightarrow F\). The diameter length is \(4\).
The center of the tree is node \(A\), because the longest chain starting from \(A\) (to \(D\) or \(F\)) is \(2\).
If \(B\) or \(C\) is taken as the root, the longest chain starting from these nodes would be longer, so they are not the tree's center.

Time Complexity

The time complexity of the above algorithm is \(O(n)\), where \(n\) is the number of nodes in the tree.

References

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