Narfouz in the Center (Editorial)

Let's root the tree at node $1$.

We define the following DP arrays:

\text{downDepth}_x: the maximum depth from $x$ to a leaf in its subtree.

\text{downDiam}_x: the diameter (in number of nodes) of the subtree rooted at $x$.

We compute them as:

Now define the upward DP:

\text{upDepth}_x: the maximum depth starting from $x$ going outside its subtree.

\text{upDiam}_x: the diameter of the tree after removing the subtree of $x$.

To compute \text{upDepth}_x (where p = \text{parent}(x)):

To compute \text{upDiam}_x, we take the maximum of:

Finally, for a node $v$, after removing it, each component corresponds to:

• each child subtree of $v$

• the remaining upper component

For each component, we compute its diameter and count centers:

Thus,

Time complexity: $O(n)$