Чтобы решить первую часть задачи и посчитать сумму расстояний для изначального метро, можно использовать динамическое программирование на дереве с переподвешиванием. Подвесим дерево за любую вершину и посчитаем для каждой вершины размер её поддерева. Далее посчитаем для каждой вершины сумму расстояний от неё до вершин её поддерева. Чтобы это сделать, переберём детей вершины, возьмём сумму расстояний от ребёнка до всех вершин его поддерева, увеличим каждое расстояние на 1, прибавив размер поддерева ребёнка, и просуммируем эту величину по всем детям вершины. В итоге мы получим сумму расстояний от корня до всех вершин. Чтобы посчитать расстояния от других вершин, применим технику переподвешивания дерева. Пусть корнем в данный момент является вершина $$$v$$$. Переберём её детей. Пусть мы сейчас рассматриваем ребёнка $$$u$$$. «Забудем», что $$$u$$$ являлся ребёнком $$$v$$$, откатив пересчёт динамики для $$$v$$$, и сделаем $$$v$$$ ребёнком $$$u$$$, пересчитав динамику $$$u$$$ через $$$v$$$. Теперь корнем является $$$u$$$, и мы знаем сумму расстояний от $$$u$$$ до всех вершин. Пройдёмся по дереву обходом в глубину, каждый раз переподвешивая дерево за ту вершину, в которой мы сейчас находимся в обходе. В итоге мы узнаем сумму расстояний от любой вершины до всех остальных, и просуммировав их, получим ответ на задачу.

Чтобы решить вторую часть, посмотрим, как изменяется сумма расстояний между всеми парами вершин в дереве при добавлении цикла длины 3. Рассмотрим цикл $$$u-w-v$$$. Пусть рёбра $$$u-w$$$ и $$$w-v$$$ в дереве уже были, а мы добавили ребро $$$u-v$$$. Тогда длины всех путей, которые раньше проходили через вершины $$$u-w-v$$$, уменьшились на 1, так как теперь можно пройти по новому ребру $$$u-v$$$. То есть, уменьшились на 1 длины всех путей от какой-либо вершины из поддерева $$$u$$$ до какой-либо вершины из поддерева $$$v$$$, если подвесить дерево за $$$w$$$, а значит, сумма расстояний уменьшилась на $$$2 \cdot sub_u \cdot sub_v$$$, где $$$sub_v$$$ — размер поддерева $$$v$$$.

Чтобы найти оптимальные $$$u$$$ и $$$v$$$, вновь применим переподвешивание. Пусть в данный момент корнем является $$$w$$$. Переберём его детей и найдём двух из них, $$$u$$$ и $$$v$$$, с максимальными размерами поддеревьев. Запомним значение $$$2 \cdot sub_u \cdot sub_v$$$ и выберем из них наибольшее по всем $$$w$$$. Асимптотика: $$$\mathcal O(n)$$$.