Вклад ребра

Задачи вида «посчитать что-то по всем парам вершин» выглядят квадратично: пар $\binom{n}{2}$, и при $n = 10^5$ это $5 \cdot 10^9$.

Спасает смена точки зрения: вместо «переберём пары и для каждой посчитаем длину пути» - «переберём рёбра и для каждого посчитаем, во скольких путях оно участвует».

Сколько путей проходит через ребро

Дерево (или лес). Удалим ребро $e$ - дерево распадётся на две части размеров $a$ и $b$. Простой путь проходит через $e$ ровно тогда, когда его концы лежат в разных частях.

$$\text{путей через } e = a \cdot b$$

Размеры считаются одним обходом: если подвесить дерево за корень, то для ребра «вершина $v$ - её предок» части равны $size[v]$ и $n_{\text{компоненты}} - size[v]$.

Что из этого следует

Сумма длин всех путей равна сумме вкладов рёбер:

$$\sum_{\text{пары}} \mathrm{dist}(u, v) = \sum_{e} a_e \cdot b_e$$

Каждое ребро на пути добавляет к его длине единицу, значит суммарная длина - это просто «сколько раз каждое ребро было пройдено».

Количество путей в лесу - это сумма $\binom{s}{2}$ по компонентам размера $s$: путь существует ровно между вершинами одной компоненты.

long long paths = 0, lengths = 0;
for (long long s : componentSizes) paths += s * (s - 1) / 2;
for (int v : vertices) if (parent[v] >= 0)
    lengths += sub[v] * (componentSize[v] - sub[v]);

Проверено: на 4000 случайных лесов до 9 вершин обе величины совпали с прямым перебором всех пар и обходом из каждой вершины.

Про типы

При $n = 10^5$ количество путей доходит до $5 \cdot 10^9$, а сумма длин - до $n^3 / 6 \approx 1{,}7 \cdot 10^{14}$ у пути-цепочки. Оба числа не помещаются в 32 бита; произведение $a \cdot b$ тоже надо считать в 64-битном типе, даже если сами $a$ и $b$ - int.

Где ещё работает тот же приём

Смена точки зрения с «объектов» на «вклады» встречается далеко за пределами деревьев:

задача	что перебирать вместо пар
сумма длин путей в дереве	рёбра
сумма минимумов по всем подотрезкам	элементы: в скольких подотрезках элемент минимален
сумма попарных расстояний на прямой	промежутки между соседними точками
количество инверсий	элементы: сколько меньших справа

Общий признак: величина по паре раскладывается в сумму по «мелким» объектам, и для каждого мелкого объекта легко посчитать, в скольких парах он участвует.