Sum of all distances in connected DAG in $O(n\log n)$
I think the question is not clear enough, but what I understood is that we want to find the sum of all the shortest path from $u$ to $v$ such that $u &lt; v$. The trick is that the graph is actually a directed chain, so we can represent the edges in an array $A$ of length $n - 1$.

The brute force formula is $\sum_{i=1}^{n -1} \sum_{j=i + 1}^{n} \delta(i,j)$. Where $\delta(i,j)$ is the shortest path from $i$ to $j$, because our graph is a chain, we can simply express this as $\delta(i,j) = \sum_{k=i}^{j - 1} A_{k}$. In the example you provided with 4 nodes $A =[1,1,1]$. The above formulas have a complexity of $\Theta(n^3)$, which can be improved to $\Theta(n^2)$ by doing a prefix sum on $A$. But a pattern can easily detected by looking carefully where the items of $A$ repeat.

For example, if $A = [1,2,3]$ the above formulas would provide the following operations:

$(1 + (1+2) + (1+2+3)) + (2 + (2+3)) + (3)$, here each "big parenthesis" is the computation from each node. The last node is obviously ignored.

We can rewrite this as:

$3 *(3 * 1) + 2 *(2 * 2) + 1 * (1 * 3)$

For example $3 *(3 * 1)$ means that $3$ was repeated once ($1$) on $3$ parenthesis. Likewise, $ 2 *(2 * 2)$ means that $2$ is repeated two times on $2$ parenthesis and so on.

The repetitions have a pattern: the number of times it appears on a "big parenthesis" is actually the index of the element, but the number of times is repeated inside the parenthesis decreases as the index increases because less paths starts from nodes that are closer to the end of the chain. Work through the example and you will find the pattern, make sure you understand this paragraph.

As you mentioned that you have not found the pattern, the above discussion can be summarized in this formula: $\sum_{i=1}^{n - 1} A_{i} * i * (n - i)$. Remember that $n$ is equal to the number of nodes and $A$ contains the edges, which are $n - 1$.

The proof of the above intuition is left as an exercise for the reader :-).

EDIT: Just in case, the complexity is $\Theta(n)$ because we only do a loop to compute the summation and the inner operations are $\Theta(1)$. Depending on how you represent the graph in the input, the memory complexity can be either $\Theta(1)$ or $\Theta(n)$.