Динамика на деревьях

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

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

void dfs(int v, int p) {
    for (int u : g[v]) if (u != p) dfs(u, v);
    // здесь все дети посчитаны — считаем состояние v
}

Дальше вся работа — понять, что именно хранить в состоянии, чтобы пересчёт был возможен.

Пример: максимальное по весу независимое множество

Независимое множество — набор вершин, никакие две из которых не соединены ребром. У вершин есть веса, надо набрать максимальный суммарный вес.

В произвольном графе эта задача NP-полна. В дереве решается за линию.

Чего не хватает, если хранить только «ответ для поддерева»? Того, взяли мы саму вершину или нет: если взяли, детей брать нельзя. Значит, признак «взяли ли $v$» входит в состояние.

$dp[v][1]$ — лучший ответ для поддерева $v$ при условии, что $v$ взята; $dp[v][0]$ — при условии, что не взята.

void dfs(int v, int p) {
    dp[v][0] = 0;
    dp[v][1] = w[v];
    for (int u : g[v]) if (u != p) {
        dfs(u, v);
        dp[v][1] += dp[u][0];                        // взяли v — детей брать нельзя
        dp[v][0] += max(dp[u][0], dp[u][1]);         // не взяли — как выгоднее
    }
}
// ответ: max(dp[root][0], dp[root][1])

Проверено: на 50 000 деревьев до двенадцати вершин совпало с перебором всех подмножеств.

Почему не жадность

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

С весами она ломается сразу. Пусть у корня двое детей-листьев с весом 100 каждый, а у самого корня вес 1000. Жадность возьмёт листья и получит 200, оптимум — взять корень и получить 1000.

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

Пример: диаметр дерева

Диаметр — наибольшее расстояние между парой вершин — ищется двумя обходами, но это решение не обобщается. Динамика обобщается.

Что хранить: $h[v]$ — глубину поддерева, то есть длину наибольшего пути вниз из $v$.

Любой путь в поддереве $v$ либо целиком лежит в поддереве одного ребёнка, либо поднимается из одного ребёнка в $v$ и спускается в другого. Первый случай уже учтён рекурсией, второй считается через две наибольшие глубины среди детей.

void dfs(int v, int p) {
    h[v] = 0;
    long long m1 = -1, m2 = -1;                      // две наибольшие глубины детей
    for (int u : g[v]) if (u != p) {
        dfs(u, v);
        long long cand = h[u] + 1;
        if (cand > m1) { m2 = m1; m1 = cand; }
        else if (cand > m2) m2 = cand;
    }
    if (m1 >= 0) h[v] = m1;
    diameter = max(diameter, (m1 > 0 ? m1 : 0) + (m2 > 0 ? m2 : 0));
}

Проверено: на 50 000 деревьев совпало с обходом из каждой вершины.

Аккуратность нужна при одном ребёнке: второго максимума нет, и его нельзя считать нулём «по умолчанию» на взвешенном дереве с отрицательными весами.

Что обобщается, а что нет

усложнение	два обхода	динамика
невзвешенное дерево	да	да
неотрицательные веса рёбер	да	да
отрицательные веса	нет	да
нужен не только ответ, но и путь	неудобно	да
ограничение на число рёбер в пути	нет	да

На взвешенном дереве с отрицательными весами приём с двумя обходами даёт неверный ответ — это стандартный контрпример к «диаметр ищется двумя обходами». В динамике меняется только +1 на +вес ребра, и при отрицательных весах второй максимум просто не берётся.

Общая схема

1. Подвесить дерево.
2. Понять, какой информации о поддереве достаточно, чтобы собрать ответ у родителя. Обычно это ответ плюс один-два признака.
3. Написать обход, в конце которого считается состояние.

Второй пункт и есть вся задача. Признак «взяли или нет», «какого цвета вершина», «сколько уже набрали» — всё это добавляется в состояние, и размер динамики умножается на число вариантов признака.

Когда признак — это количество, получается дерево-рюкзак, и у него неожиданная асимптотика.