Let's consider a directed rooted tree $T$ and define a function $f\colon V(T) \to \mathbb N$ equal for each vertex $v$ to the distance to the nearest leaf (in the subtree with root $v$). Formally $$f(v) = \min_{u \in V(T) \mid \deg^+ u = 0 \land \exists (v, u)\text{-path}} d(v, u),$$ or equivalently $$f(v) = \begin{cases}0, & \text{if } \deg^+ v = 0,\\ 1 + \min_{u \in N^+(v)} f(u), & \text{otherwise.}\end{cases}$$ (Here $\deg^+ v$ means outdegree of the vertex $v$ and $N^+(v)$ means out-neighborhood of the vertex $v$.)
The question is: for a given order $|T| = n$ of the tree what is the maximum possible sum of $f(v) \cdot \deg^+ v$ over all $v$ with outdegree $\deg^+ \ge 2$? Or more simple version, is it true that $$\sum_{v \in V(T) \mid \deg^+ v \ge 2} f(v) \cdot \deg^+ v = \mathrm O(n)?$$
This question arose from my solution of an algorithmic problem. During competition I had an intuition that $$\sum_{v \in V(T) \mid \deg^+ v \ge 2} f(v) \cdot \deg^+ v = \mathrm O(n \log n)$$ and the corresponding running time of my algorithm could be good enough. After the competition I proved this bound, however I failed to find such an extreme example of a tree sequence. Now I have a conjecture that this sum is $\mathrm O(n)$, but I failed to prove or disprove it.
My proof of $\mathrm O(n \log n)$ bound is based on heavy-light decomposition. Note that sum over all vertices of the main path (i. e., going from the root to a leaf along heavy arcs only) never exceeds $2n$, because on one hand a summand at the vertex $v$ doesn't exceed the double number of vertices in a subtree with root at light son of $v$ and on the other hand no vertex appears twice in such subtrees when we move along heavy arcs only. After removing vertices of this path we get a forest in which each tree has an order of at most $n / 2 - 1$. Now we do the same with main paths for all remaining trees together. Sum of orders of these trees is less than $n$, therefore sum of $f(v) \cdot \deg^+ v$ over all vertices $v$ of these paths is less than $2n$. Repeating this step at most $\log_2 n$ times we remove all vertices, getting that the total sum is less than $2n \log_2 n$.