DP на дереве — это класс задач, где значения в вершине вычисляются на основе значений её детей в DFS-дереве.
Диаметр — длина максимального простого пути между двумя вершинами дерева.
Классическая DP-идея:
Для каждой вершины считаем:
Тогда путь, проходящий через :
Глобальный диаметр — максимум по всем .
Нужно для каждой вершины найти длину максимального пути, проходящего через неё.
Путь через вершину может идти:
Поэтому делается rerooting DP:
Паросочетание — набор рёбер без общих вершин.
DP по дереву:
Для вершины считаем:
Переходы:
Итого:
Ответ в корне:
Это классическая задача maximum matching in tree за .
Также заметим, что существует жадное решение, где в каждый момент берется лист и матчится с предком до тех пор пока можно. Это можно реализовать с помощью одним проходом DFS.
Выберем любую вершину .
Тогда путь — диаметр дерева.
Пусть есть подмножество вершин дерева. Вершины добавляются по одной.
Утверждение:
Существует две вершины , такие что для любой вершины :
То есть диаметр множества всегда задаётся парой вершин.
При добавлении новой вершины достаточно проверить:
И обновить пару при необходимости.
Это свойство используется в задачах:
void dfs(int x, int p) {
for (int y: v[x]) {
if (y == p) {
continue;
}
dfs(y, x);
down[x] = max(down[x], down[y] + 1);
}
}
void dfs2(int x, int p) {
vector<pair<int, int>> g;
/*
We can change this logic to linear by
keeping two furthest only
*/
for (int y: v[x]) {
if (y == p) {
continue;
}
g.push_back({down[y] + 1, y}); // distance to x
}
g.push_back({0, -1});
sort(g.rbegin(), g.rend());
for (int y: v[x]) {
if (y == p) {
continue;
}
up[y] = up[x] + 1;
if (g[0].second == y) {
up[y] = max(up[y], g[1].first + 1);
} else {
up[y] = max(up[y], g[0].first + 1);
}
dfs2(y, x);
}
}