5. In the country, there are 100 cities, and several non-stop air routes are in operation between them, such that one can travel from any city to any other, possibly with layovers. For each pair of cities, the minimum number of flights required to travel from one to the other was calculated. The transportation difficulty of the country is defined as the sum of the squares of these 4950 numbers. What is the maximum value that the transportation difficulty can take? The answer should be given as a number (in decimal notation).
Solution. First, we prove that the maximum transportation difficulty occurs when the cities are connected "in a chain."

Indeed, we can consider the graph as a tree (otherwise, we can remove some edges to leave a tree - the difficulty will increase). Choose the longest path in the tree. Suppose there are vertices not included in this path. Then among them, there is a pendant vertex $x$ (i.e., a vertex with only one edge leading to it). Let $y$ be the vertex on the longest path closest to $x$. Move the entire "branch" extending from $y$ and containing $x$ to the end of the longest path, the farthest from $y$. Note that as a result, the pairwise distances between the vertices within the "branch" do not change, nor do the distances between the vertices outside the branch. It is easy to see that for each vertex in the branch, the sum of the squares of the distances to all other vertices has increased. Indeed, if $k$ is the distance from some vertex $z$ in the branch to $y$, then the set of distances from $z$ to the vertices outside the branch (including $y$) was $k, k+1, k+1, k+2, k+2, \ldots, k+s, k+s, k+s+1, k+s+2, \ldots$, and it became $k, k+1, k+2, k+3, \ldots$

![](https://cdn.mathpix.com/cropped/2024_05_06_5f3f20df45781134e3a1g-3.jpg?height=244&width=1510&top_left_y=1247&top_left_x=337)

By such "re-hangings," we can bring the graph to the form of a chain, and the difficulty will always increase; hence, for the chain, it is maximal.

Now we calculate the difficulty for the "chain." The problem reduces to finding the sum $99 \cdot 1^{2} + 98 \cdot 2^{2} + 97 \cdot 3^{2} + \ldots + 1 \cdot 99^{2}$.

Let $S_{n}^{2} = 1^{2} + 2^{2} + \ldots + n^{2}$, $S_{n}^{3} = 1^{3} + 2^{3} + \ldots + n^{3}$. As is known, $S_{n}^{2} = \frac{n(n+1)(2n+1)}{6}$, $S_{n}^{3} = \left(\frac{n(n+1)}{2}\right)^{2}$ (this can be proven by induction).

Notice that the desired sum is equal to

$$
\begin{gathered}
100 \cdot \left(1^{2} + 2^{2} + \ldots + 99^{2}\right) - \left(1 \cdot 1^{2} + 2 \cdot 2^{2} + \ldots + 99 \cdot 99^{2}\right) = 100 S_{99}^{2} - S_{99}^{3} = \\
= 100 \cdot \frac{99 \cdot (99+1) \cdot (2 \cdot 99 + 1)}{6} - \left(\frac{99 \cdot (99+1)}{2}\right)^{2} = 32835000 - 24502500 = 8332500.
\end{gathered}
$$