DP на деревьях

O(n)

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

Сигналы

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

Шаблон

function maxNonAdjacent(node) {
    if (!node) return [0, 0]; // [incl, excl]
    let inclSum = node.value;
    let exclSum = 0;
    for (const child of node.children) {
        const [inclC, exclC] = maxNonAdjacent(child);
        inclSum += exclC;
        exclSum += Math.max(inclC, exclC);
    }
    return [inclSum, exclSum];
}

Похоже, но не то

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

n до 1e5 узлов, один постпорядковый визит на узел с парой возвращаемых чисел -> O(n): каждый узел объединяет состояния своих детей ровно один раз.

Изучить этот паттерн