Допустим дана есть дерево и какая-то задача с ним. Мы умеем за какую-то приемлимую асимптотику (например, за линию) находить ответ для корня. Но пускай надо решить задачу для каждой вершины. Можно для каждой вершины запустить наше решение, но это решение будет за \(O(n^2)\). Заметим, что многие данные у соседних вершин схожи. Используем это.
Дано дерево, состоящее из \(n\) вершин. Некоторые вершины покрашены в черный цвет. Для каждой вершины найдите расстояние до ближайшей чёрной вершины.
Давайте сначала решим задачу для одной вершины. Подвесим дерево за нее. Сделаем такое простое ДП:
\begin{equation*} dp_u = \begin{cases} 0 &\text{$u$ покрашена}\\ min(dp_v)+1 &\text{$v$ ребенок $u$}\\ +\infty &\text{$u$ лист} \end{cases} \end{equation*}
Хорошо, мы умеем уже решать за квадрат эту задачу. Вот мы насчитали для корня какую-то информацию. Давайте попробуем перейти от корня к какому-то из детей корня (теперь будем считать что эта вершина станет новым корнем). Легко заметить, что все остальные дети корня будут участвовать в ответе для нового корня. Возьмем из них минимальный и передадим этой вершине.
Вполне логичным возникает следующий рекурсивный алгоритм (при учете того, что мы уже отдельно насчитали массив \(dp\)): присвоить ответу для текущей вершины минимум их \(dp_u\) и параметра \(x\) который мы передаем рекурсивно, выписать все \(dp_v\) детей, запуститься от каждого из детей передав минимальное значение из выписанного массива (не считая значение этого ребенка) прибавив \(2\) (ровно такое расстояние между детьми одной вершины).
vector< int > tree[MAXN];
int is_colored[MAXN], dp[MAXN], ans[MAXN];
void dfs1(int w, int p=-1) {
dp[w] = inf;
for(auto to: tree[w]) if(to != p) {
dfs1(to, w);
dp[w] = min(dp[w], dp[to]+1);
}
if(is_colored[w]) dp[w] = 0;
}
void dfs2(int w, int p=-1, int x=1e9) {
ans[w] = min(dp[w], x);
int min1 = x;
for(auto to: tree[w]) if(to != p)
min1 = min(min1, dp[to]+1);
for(auto to: tree[w]) if(to != p)
dfs2(to, w, min1+1);
}
dfs1(0);
dfs2(0);
Допустим нам нужно как-то манипулировать с глубинами (расстоянием от корня до вершины) различных вершин в процессе подсчета. Давайте подвесим дерево за какой-то корень, выпишем глубины вершин в порядке эйлерового обхода. Заметим, что когда мы будем переподвешивать вершину за очередного ребенка расстояние до всех вершин увеличится на \(1\), а расстояние до вершин в поддереве уменьшится на \(1\). Вспомним, что в эйлеровом обходе любое поддерево является непрерывным отрезком. Теперь мы можем использовать ДО для прибавления на отрезке.
Допустим мы хотим поддерживать также и LA при переподвешивании. Можно один раз посчитать массив \(binup[i][k]\) - \(2^k\)-й предок вершины \(i\) при изначальном корне. Теперь заметим, что чтобы найти \(x\)-го предка вершины \(v\), при другом корне, надо рассмотреть путь между ними в изначальном дереве. Найдем LCA корня и вершины и посмотрим лежит ли вершина на пути между корнем и LCA или LCA или вершиной. Рассмотрев случаи найдем ответ.
Соответственно можно находить и LCA.