Tree Centroid

A vertex $T$ of a tree $v$ is a centroid if and only if any one of the following holds:

Unrooted-tree version

1. After deleting $v$, every component of $T\setminus\{v\}$ has size at most half the original tree size.

2. Among the largest-component sizes obtained by deleting one vertex, deleting $v$ gives the minimum.

3. Among the sums of distances from all vertices to one vertex, the sum of distances to $v$ is minimum.

Rooted-tree version

1. When rooted at $v$, every proper subtree has size at most half the original tree size.
2. Among the largest proper-subtree sizes over all possible roots, rooting at $v$ gives the minimum.
3. Among the sums of depths from all vertices over all possible roots, rooting at $v$ gives the minimum.

Introduce notation. The rooted and unrooted formulations are equivalent. Let $W(x)=\max_{u\sim x}|T_u^{(x)}|$, where $u\sim x$ means adjacent, and let $u$, where $x$ is the distance between $S(x)=\sum_{u\in T}d(u,x)$ and $d(u,x)$. Definitions 1, 2, and 3 require $u$, $x$, and $W(v)\le |T|/2$, respectively. We prove their equivalence. $v\in\arg\min_{x\in T}W(x)$ $v\in\arg\min_{x\in T}S(x)$

Interpret $S(x)$ as the sum of depths when rooted at $x$. Move the root from $v$ to an adjacent vertex $u$. Deleting $(v,u)$ leaves $T_v^{(u)}$ and $T_u^{(v)}$; depths in the first increase by $T_v^{(u)}$ and depths in the second decrease by $1$, so the change in depth sum is: $T_u^{(v)}$ $1$

Thus Definition 1 is equivalent to requiring $\Delta S_{v\to u}\le 0$ for every neighbor $v$ of $u$, meaning that $v$ is a local minimum of $S(x)$.

Conversely, let $v$ be a global minimum of $S(x)$, as in Definition 3. Consider the rooted tree $v$. Let $T^{(v)}$ be a non-root vertex; let $u\neq v$ be the successor of $v$ on the path from $u$ to $v$, and $y$ the predecessor of $u$ (possibly $u$). Since $x$, we obtain: $v$ $T_u^{(x)}\subseteq T_y^{(v)}$

The last step uses the fact that $v$ is a local minimum of $S(x)$. There are two cases:

• Some $u$ satisfies $2|T_x^{(u)}|=|T|$. Then the inequality forces $(x,u)=(v,y)$ and $|T_v^{(u)}|=|T_{u}^{(v)}| = |T|/2$. Such a vertex $u$ is unique and adjacent to $v$; every other $u'\neq u,v$ has an $x'\sim u'$ with $|T_{x'}^{(u')}| > |T|/2$. Thus the vertices satisfying Definition 1 are $\{v,u\}$.

  Deleting any vertex leaves components whose sizes sum to $|T|-1$. If one component has size at least $|T|/2$, it is the largest. Hence $W(v)=W(u)=|T|/2$ and every other $u'\neq u,v$ has $W(u') > |T|/2$, so the vertices satisfying Definition 2 are $\arg\min W(x) = \{v,u\}$.

  Since $\Delta S_{v\to u} = 0$, $S(v)=S(u)$, so $v$ is also a global minimum. Every other $u$ has an $u'\neq u,v$ with $x'\sim u'$, contradicting local minimality. Thus the vertices satisfying Definition 3 are $|T_{x'}^{(u')}| > |T|/2$. $u'$ $\arg\min S(x) = \{v,u\}$

• No $u$ satisfies $2|T_x^{(u)}|=|T|$. Then every $u\neq v$ has $x\sim u$ with $|T_x^{(u)}| > |T|/2$. The preceding argument gives $u\neq v$ and shows that $W(u) > |T|/2$ is not a local minimum, so only $u$ satisfies Definition 1 and $S(x)$. $v$ $\arg\min W(x)=\arg\min S(x) = \{v\}$

In both cases the three sets coincide, proving that the definitions are equivalent.

1. If a tree has more than one centroid, it has exactly two. They are adjacent, and deleting their connecting edge leaves two components of equal size.
2. Adding or deleting one leaf moves a centroid by at most one edge.
3. When two trees are joined by an edge, a centroid of the new tree lies on the path between centroids of the original trees.
4. A rooted tree's centroid lies on the heavy chain containing the root. The centroid of a tree is an ancestor of the centroid of the subtree rooted at the root's heavy child.

Property 1 follows from the proof of the equivalent definitions.

For Property 2, consider adding a leaf. There are two cases:

• centroid $T$ centroid $v$．centroid $x$ centroid，centroid $v$ centroid $T\cup\{x\}\setminus\{v\}$ centroid，$x$ centroid $B\cup\{x\}$．centroid $v$ centroid $T$ centroid，centroid $2|B| < |T|$，centroid $2|B|+1\le |T|$．centroid，centroid

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

  Therefore $v$ remains a centroid of $T\cup\{x\}$. Even if the new tree has two centroids, the other is adjacent to $v$, so the centroid moves by at most one edge.

• Suppose $T$ has two centroids $u,v$. Deleting $(u,v)$ gives equal components $T_u^{(v)}$ and $T_v^{(u)}$, each of size $|T|/2$. Assume the new leaf $x$ is attached to $v$. $T_v^{(u)}$

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

  Thus $u$ is no longer a centroid. Conversely, after deleting $v$, the component $|T|/2$ still has size $T_u^{(v)}$, while the other components have total size:

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

  Hence $v$ remains a centroid. The new tree has an odd number of vertices, so its centroid is unique and moves by at most one edge.

In both cases, the new centroid lies on the path from an old centroid to the newly added leaf.

Property 3 follows by induction. Let the new edge joining $T$ and $T'$ be $(x,y)$ with $x\in T,y\in T'$ and $T$. Assume a centroid of the new tree lies in $T$. Add the vertices of $T'$ one leaf at a time. Property 2 shows inductively that the centroid remains on the path from the centroid of $T$ to $x$. $v$ $v$ $T$ $T$ $v$ $x$ $v$ $T$ $x$ $v$ $x$

Property 4 follows from the heavy-light decomposition properties. Let $T$ be a centroid of $v$. If $v$ is the root, this is immediate. Otherwise let $v$ be its parent. Since $u$, the subtree containing $|T_u^{(v)}| \le |T|/2$ has size at least $v$. Crossing a light edge on the path to the root would make it smaller than $|T|/2$, a contradiction; hence $|T|/2$ lies on the root's heavy chain. The heavy-child construction and Property 3 then show that the new centroid is an ancestor of the old one.

By Property 3, the centroid of a subtree rooted at $u$ lies on a path from the centroid of a subtree rooted at one of $u$'s direct children to $u$.

As in the DFS method above, first find the centroids of all subtrees rooted at direct children of $u$ (a leaf's centroid is itself), then move upward along the path and test which vertices are centroids.

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

#include <iostream>
#include <vector>
using namespace std;

constexpr int N = 3e5 + 5;

int n, q;  // number of vertices and queries
int fa[N];
vector<int> son[N];
int siz[N],     // subtree sizes
    ans[N],     // centroid of the subtree rooted at u is ans[u]
    weight[N];  // vertex 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;
}