Смена корня

Динамика на дереве считает ответ для корня. Но часто спрашивают ответ для каждой вершины: сумму расстояний до остальных, наибольшее удаление, число путей через вершину.

Запускать динамику из каждой вершины - $O(n^2)$: при $n = 10^5$ безнадёжно. Приём смены корня (его же называют перевешиванием) считает всё за два обхода.

Идея

Подвесим дерево за вершину 0 и посчитаем обычную динамику снизу вверх: $down[v]$ - ответ по поддереву $v$.

Теперь заметим: если ответ для вершины $v$ уже известен, то ответ для её ребёнка $c$ отличается от него предсказуемо. Всё дерево делится ребром $(v, c)$ на две части, и при переходе от $v$ к $c$ одна часть приближается, а другая отдаляется.

Значит, второй обход - сверху вниз - пересчитывает ответ по одной формуле на ребро.

Пример: сумма расстояний

Пусть $ans[v]$ - сумма взвешенных расстояний от $v$ до всех вершин.

Первый обход даёт размеры поддеревьев и суммы внутри них:

size[v] = 1;
down[v] = 0;
for (auto [c, w] : children[v]) {
    size[v] += size[c];
    down[v] += down[c] + (long long)w * size[c];
}

Второй обход: $ans[0] = down[0]$, а для ребёнка $c$ вершины $v$ с весом ребра $w$

$$ans[c] = ans[v] + w \cdot (n - 2 \cdot size[c])$$

Формула читается так: при переходе из $v$ в $c$ все $size[c]$ вершин поддерева приблизились на $w$, а остальные $n - size[c]$ отдалились на $w$. Разность и даёт $w \cdot ((n - size[c]) - size[c])$.

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

Когда обход вниз недостаточен

В сумме расстояний вклад «всего остального» уместился в одно число. Так бывает не всегда: если операция сборки не обратима, вычесть вклад ребёнка из уже посчитанного $down[v]$ не получится.

Типичный пример - максимум. Пусть $up[v]$ - ответ по части дерева вне поддерева $v$. Тогда

$$up[c] = w + \max\bigl(up[v],\ \max_{c\, '\, \ne\, c} (down[c'] + w_{c'})\bigr)$$

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

Общее правило: сборка должна быть либо обратимой (сумма, произведение по модулю, xor), либо допускать «всё, кроме одного» через префиксы и суффиксы по списку детей.

Схема

1. Обход вниз: посчитать $down[v]$ и всё, что нужно для перехода (размеры, два максимума).
2. Обход вверх: положить $ans[\text{корень}] = down[\text{корень}]$ и пересчитать детей по формуле.

Оба обхода стоят $O(n)$, память тоже. Рекурсию при $n = 10^5$ лучше развернуть в явный стек: глубина дерева бывает равна $n$.