Algorithmic Problem on Trees

Given a directed, rooted tree with $$n$$ vertices, the height of a vertex $$v$$, $$h[v]$$ is the number of edges on the longest path from $$v$$ to some reachable leaf node. Give an efficient algorithm to find the following,

$$d[v] := \max\limits_{w \text{ is a sibling of v}} h[w] \qquad \forall v \in V.$$

Note: The algorithm I was able to come up is the trivial one.

1. Finds the height of all vertices using DFS.
2. Do a BFS from the root and store all the vertices to a particular distance in a map.
3. Go over the list for every element $$v$$ and find the maximum using the expression above.

Can we do better than this?

• Can you state how, for a parent $u$, $d[v]$ of all its children $v$ relates to $d[u]$? What about $h(u)$? Can you give an algorithm using less additional storage than your first stab? Dec 7 '21 at 16:37

Now to the main question - this algorithm is optimal. The runtime of each step is $$O(n)$$, and thus the entire algorithm takes $$O(n)$$.
But notice that the problem requires you to output a value for each node - and thus any algorithm will have to spend at least $$\Omega(n)$$ time printing the output.