AIOJ

Definition

In a tree, if the longest path starting from vertex $x$ , when $x$ is chosen as the root, is as short as possible, 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 if there are two, they are adjacent.
The center of a tree always lies on the tree's diameter.
The paths from every vertex of a tree to its farthest vertex always meet at the tree's center.
When the center of a tree is the root, the two paths from it to the endpoints of the diameter are the longest and second-longest paths, respectively.
When two trees are merged by adding an edge between them, connecting their centers minimizes the diameter of the resulting tree.
The distance from the center of a tree to any other vertex is at most half the tree's diameter.

Finding the center

Find a vertex $x$ for which the longest path starting from it, when it is the root, is as short as possible.

Steps

Maintain $len1_x$ , the longest path within the subtree of vertex $x$ .
Maintain $len2_x$ , the longest path that does not overlap with $len1_x$ .
Maintain $up_x$ , the longest path outside the subtree of vertex $x$ ; this path must pass through the parent of $x$ .
Find the vertex $x$ that minimizes $\max(len1_x, up_x)$ ; this $x$ is the center of the tree.

Reference implementation

// Vertices are numbered from 1, so i ∈ [1,n]; the graph uses vector storage.
int d1[N], d2[N], up[N], x, y, mini = 1e9;  // d1 and d2 correspond to len1 and len2 above

struct node {
  int to, val;  // to is the endpoint and 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 endpoint of this edge and val is its weight
    if (nxt == fa) {
      continue;
    }
    dfsd(nxt, cur);
    if (d1[nxt] + w > d1[cur]) {  // can update the longest path
      d2[cur] = d1[cur];
      d1[cur] = d1[nxt] + w;
    } else if (d1[nxt] + w > d2[cur]) {  // cannot update the longest path, but can update the second-longest path
      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 path in this subtree is not in the nxt subtree
      up[nxt] = max(up[nxt], d1[cur] + w);
    } else {  // if the longest path in this subtree is in the nxt subtree, use the second-longest path
      up[nxt] = max(up[nxt], d2[cur] + w);
    }
    dfsu(nxt, cur);
  }
}

void GetTreeCenter() {  // find the tree's centers, denoted by x and y if they exist
  dfsd(1, 0);
  dfsu(1, 0);
  for (int i = 1; i <= n; i++) {
    if (max(d1[i], up[i]) < mini) {  // found a vertex minimizing the current max(len1[x],up[x])
      mini = max(d1[i], up[i]);
      x = i;
      y = 0;
    } else if (max(d1[i], up[i]) == mini) {  // the other center
      y = i;
    }
  }
}

Example

Suppose we have the following tree:

The tree's diameter is $D \rightarrow B \rightarrow A \rightarrow C \rightarrow F$ , with length $4$ .
The center of the tree is vertex $A$ , because the longest paths from $A$ (to $D$ or $F$ ) both have length $2$ .
If $B$ or $C$ is chosen as the root, the longest path from that vertex becomes longer, so neither is the center of the tree.

Time complexity

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

Center of a Tree