DP на дереве (Tree DP) - Course 4

Module 1: Trie

БОР

Module 2: Sparse Table

Разреженная таблица

Module 3: Segment Tree

Дерево отрезков
Максимальная сумма подотрезка на заданном отрезке

Module 4: Segment Tree Lazy propagation

Segment Tree с Lazy Propagation

Module 5: More on trees

Euler порядок посещений вершин
DP на дереве (Tree DP)

Module 6: Binary jumping

Двоичные подъёмы (прыжки)
Наименьший общий предок

Module 7: Cyclic Games

Игры на циклических графах

Module 8: Divide & Conquer

Разделяй и властвуй

Module 9: SQRT Techniques

SQRT Декомпозиция
Корневые эвристики
Алгоритм Мо

Главная Курсы Ресурсы Задачи Национальная олимпиада Соревнования Таблица лидеров

...

Главная/Courses/Course 4/Module 5: More on trees/DP на дереве (Tree DP)

DP на дереве (Tree DP)

DP на дереве — это класс задач, где значения в вершине вычисляются на основе значений её детей в DFS-дереве.

Диаметр дерева

Диаметр — длина максимального простого пути между двумя вершинами дерева.

Классическая DP-идея:

Для каждой вершины $x$ считаем:

$down[x]$ — максимальная глубина пути вниз (до любого потомка)

Тогда путь, проходящий через $x$ :

$best[x] = \text{две наибольшие глубины среди детей } x + 2$

наибольшие

глубины

среди

детей

x

+

2

Глобальный диаметр — максимум по всем $best[x]$ .

Самый длинный путь через каждую вершину

Нужно для каждой вершины $x$ найти длину максимального пути, проходящего через неё.

Путь через вершину может идти:

вниз в один поддерево
вниз в два разных поддерева
вверх к предкам

Поэтому делается rerooting DP:

Считаем вниз: $down[x]$
Считаем вверх: $up[x]$ — лучший путь через родителя
Ответ для вершины:

$ans[x] = \max(\text{две лучшие глубины вокруг } x)$

Максимальное паросочетание в дереве

Паросочетание — набор рёбер без общих вершин.

DP по дереву:

Для вершины $x$ считаем:

$dp0[x]$ — максимум в поддереве $x$ , если $x$ не сматчена с родителем
$dp1[x]$ — максимум, если $x$ сматчена с одним из детей

Переходы:

$dp0[x]$ — сумма максимумов по детям
$dp1[x]$ — выбрать ребёнка $y$ и сматчить $(x,y)$

Итого:

$dp1[x] = \max_y \left( 1 + dp0[y] + \sum_{z \ne y} \max(dp0[z], dp1[z]) \right)$

Ответ в корне:

$\max(dp0[root], dp1[root])$

Это классическая задача maximum matching in tree за $O(n)$ .

Также заметим, что существует жадное решение, где в каждый момент берется лист и матчится с предком до тех пор пока можно. Это можно реализовать с помощью одним проходом DFS.

Интересное свойство диаметра

Часть 1

Выберем любую вершину $x$ .

Найдём самую дальнюю от неё вершину $y$
Найдём самую дальнюю от $y$ вершину $z$

Тогда путь $(y,z)$ — диаметр дерева.

Часть 2

Пусть есть подмножество вершин $S$ дерева. Вершины добавляются по одной.

Утверждение:

Существует две вершины $a, b \in S$ , такие что для любой вершины $v \in S$ :

$dist(a,b) = \max_{u,w \in S} dist(u,w)$

То есть диаметр множества всегда задаётся парой вершин.

При добавлении новой вершины $v$ достаточно проверить:

$dist(v,a),\quad dist(v,b)$

И обновить пару $(a,b)$ при необходимости.

Это свойство используется в задачах:

динамический диаметр множества вершин
онлайн добавление вершин
задачи на расстояния в дереве

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);
    }
}