Tree DP | kz-maxx

DP ағашта деген не?

DP ағашта — бұл динамикалық программалау. Мұнда әр вершина үшін answer немесе state есептеледі.

Көбіне біз DFS жүргіземіз және әр вершина поддеревосы үшін dp[v] мәнін санаймыз.

алдымен child вершина жауаптарын санаймыз
кейін солар арқылы parent жауабын санаймыз

Негізгі правило: dp[v] санау үшін алдымен v-ның барлық child dp-лары дайын болуы керек.

Ағаш деген не?

Ағаш — connected graph және ішінде cycle жоқ.

Егер ағашта n вершина болса, онда ребро саны әрқашан n - 1.

tree = connected graph + cycle жоқ
edge саны = n - 1

Ағаштың root-ы

DP жасау үшін ағашты бір root-қа байлап аламыз. Көбіне root ретінде 1 вершинасын аламыз.

dfs(1, 0);

Сонда әр вершина үшін:

parent — ата-анасы
children — балалары
subtree — сол вершинадан төмен тұрған бөлік

Ағаштағы базовый DFS

Ағашта cycle жоқ. Бірақ реброларды екі жаққа сақтасақ, parent-қа қайта кірмеу керек.

void dfs(int v, int p) {
    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        dfs(to, v);
    }
}

Мұнда:

v — қазіргі вершина
p — parent вершина
to — көрші вершина

Tree DP негізгі схемасы

void dfs(int v, int p) {
    // dp[v] үшін бастапқы мән

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        dfs(to, v);

        // dp[v] мәнін dp[to] арқылы жаңартамыз
    }
}

Ең маңызды идея: алдымен dfs(to), содан кейін ғана dp[to]-ды қолданамыз.

Задача 1: поддерево size

Әр вершина үшін оның поддерево size-ын табу керек.

State:

dp[v] = v вершинасының поддерево size-ы

Әр вершина өзі size-қа 1 береді:

dp[v] = 1;

Кейін барлық child size-ын қосамыз:

dp[v] += dp[to];

Код: поддерево size

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
vector<int> g[N];
int dp[N];

void dfs(int v, int p) {
    dp[v] = 1;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        dfs(to, v);
        dp[v] += dp[to];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);

    for (int i = 1; i <= n; i++) {
        cout << dp[i] << ' ';
    }

    return 0;
}

Поддерево size мысалы

Input

Root 1 болса, ағаш былай:

1
├── 2
└── 3
├── 4
└── 5

Поддерево size:

dp[1] = 5
dp[2] = 1
dp[3] = 3
dp[4] = 1
dp[5] = 1

Задача 2: көрші емес вершинадан максималды сумма

Ағаш берілген. Әр вершинада w[v] weight бар. Вершиналарды таңдау керек, бірақ көрші екі вершина бірге таңдалмауы керек. Сумма максималды болсын.

Бұл Maximum Independent Set on Tree деп аталады.

егер v вершинасын таңдасақ
онда оның child-тарын таңдай алмаймыз

Independent Set state-тері

Әр вершина үшін екі мән сақтаймыз:

dp[v][0]
dp[v][1]

dp[v][0] — v таңдалмаған кездегі v поддеревосындағы max answer
dp[v][1] — v таңдалған кездегі v поддеревосындағы max answer

Переход

Егер v таңдалса, child таңдалмайды:

dp[v][1] += dp[to][0];

Егер v таңдалмаса, әр child таңдалуы да, таңдалмауы да мүмкін:

dp[v][0] += max(dp[to][0], dp[to][1]);

Бастапқы мән:

dp[v][1] = w[v];
dp[v][0] = 0;

Код: Maximum Independent Set

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
vector<int> g[N];
long long w[N];
long long dp[N][2];

void dfs(int v, int p) {
    dp[v][0] = 0;
    dp[v][1] = w[v];

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        dfs(to, v);

        dp[v][0] += max(dp[to][0], dp[to][1]);
        dp[v][1] += dp[to][0];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }

    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);

    cout << max(dp[1][0], dp[1][1]);

    return 0;
}

Мысал

Input

Таңдауға болады:

1, 4, 5
сумма = 10 + 7 + 8 = 25

Output

Задача 3: Minimum Vertex Cover

Минималды вершина санын таңдау керек. Әр реброның кемінде бір ұшы таңдалған болуы керек.

Бұл Minimum Vertex Cover on Tree.

әр edge a--b үшін
a немесе b таңдалуы керек

Vertex Cover state-тері

dp[v][0]
dp[v][1]

dp[v][0] — v таңдалмаған кездегі minimum answer
dp[v][1] — v таңдалған кездегі minimum answer

Егер v таңдалмаса, барлық child міндетті түрде таңдалуы керек.

dp[v][0] += dp[to][1];

Егер v таңдалса, child таңдалуы да, таңдалмауы да мүмкін.

dp[v][1] += min(dp[to][0], dp[to][1]);

Код: Minimum Vertex Cover

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
vector<int> g[N];
int dp[N][2];

void dfs(int v, int p) {
    dp[v][0] = 0;
    dp[v][1] = 1;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        dfs(to, v);

        dp[v][0] += dp[to][1];
        dp[v][1] += min(dp[to][0], dp[to][1]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);

    cout << min(dp[1][0], dp[1][1]);

    return 0;
}

Задача 4: поддерево биіктігі

Әр вершина үшін оның поддерево биіктігін табу керек.

State:

dp[v] = v поддеревосының биіктігі

Егер вершинада child жоқ болса, биіктігі 1.

Әйтпесе:

dp[v] = max(dp[to] + 1)

Код: поддерево биіктігі

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
vector<int> g[N];
int dp[N];

void dfs(int v, int p) {
    dp[v] = 1;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        dfs(to, v);

        dp[v] = max(dp[v], dp[to] + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);

    for (int i = 1; i <= n; i++) {
        cout << dp[i] << ' ';
    }

    return 0;
}

Задача 5: tree diameter арқылы DP

Tree diameter — ағаштағы екі вершина арасындағы ең ұзын distance.

Оны DP арқылы табуға болады.

Әр вершина үшін child-тардан келетін екі ең үлкен height сақтаймыз.

ең ұзын path v арқылы өтуі мүмкін
бір поддереводан екінші поддеревоға

Диаметр идеясы

best1 және best2 — child-тардан келетін екі максималды depth.

v арқылы өтетін possible diameter:

best1 + best2

Ал parent үшін height:

dp[v] = best1;

Код: ағаш диаметрі

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
vector<int> g[N];
int dp[N];
int ans = 0;

void dfs(int v, int p) {
    int best1 = 0;
    int best2 = 0;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        dfs(to, v);

        int cur = dp[to] + 1;

        if (cur > best1) {
            best2 = best1;
            best1 = cur;
        } else if (cur > best2) {
            best2 = cur;
        }
    }

    dp[v] = best1;
    ans = max(ans, best1 + best2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);

    cout << ans;

    return 0;
}

Бұл код диаметрді edge саны бойынша есептейді. Егер vertex саны керек болса, answer = ans + 1.

Tree DP рекурсивный метод

Tree DP көбіне рекурсия арқылы жазылады.

Біз DFS шақырамыз:

dfs(v, parent)

DFS ішінде dp[v] санаймыз.

Бұл ыңғайлы, себебі ағаш өзі дұрыс order береді:

leaf бірінші есептеледі
parent кейін есептеледі
root ең соңында есептеледі

Итеративный методқа қалай ауыстырамыз?

Кейде recursion depth үлкен болып, stack overflow болуы мүмкін. Онда итеративный DFS қолдануға болады.

Идея:

1. Алдымен traversal order аламыз
2. Кейін order-ды reverse жасаймыз
3. Сонда child parent-тен бұрын өңделеді

DP үшін итеративный order

vector<int> order;
vector<int> parent(n + 1, 0);

stack<int> st;
st.push(1);
parent[1] = -1;

while (!st.empty()) {
    int v = st.top();
    st.pop();

    order.push_back(v);

    for (int to : g[v]) {
        if (to == parent[v]) {
            continue;
        }

        parent[to] = v;
        st.push(to);
    }
}

reverse(order.begin(), order.end());

reverse жасағаннан кейін алдымен children, кейін parents келеді. Бұл DFS postorder сияқты.

Поддерево size үшін итеративный DP

for (int v : order) {
    dp[v] = 1;

    for (int to : g[v]) {
        if (to == parent[v]) {
            continue;
        }

        dp[v] += dp[to];
    }
}

Итеративный толық реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
vector<int> g[N];
int parent[N];
int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<int> order;
    stack<int> st;

    st.push(1);
    parent[1] = -1;

    while (!st.empty()) {
        int v = st.top();
        st.pop();

        order.push_back(v);

        for (int to : g[v]) {
            if (to == parent[v]) {
                continue;
            }

            parent[to] = v;
            st.push(to);
        }
    }

    reverse(order.begin(), order.end());

    for (int v : order) {
        dp[v] = 1;

        for (int to : g[v]) {
            if (to == parent[v]) {
                continue;
            }

            dp[v] += dp[to];
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << dp[i] << ' ';
    }

    return 0;
}

Tree DP қалай ойлап табамыз?

Көбіне мына сұрақтарға жауап береміз:

1. dp[v] нені білдіреді?
2. 0/1 state керек пе?
3. Егер v таңдалса не болады?
4. Егер v таңдалмаса не болады?
5. Child answers қалай біріктіріледі?
6. Answer dp[1]-де ме, әлде max/min керек пе?

Типтік state-тер

State	Мағынасы
dp[v]	v поддеревосы үшін answer
dp[v][0]	v таңдалмаған кездегі answer
dp[v][1]	v таңдалған кездегі answer
subtree[v]	v поддеревосының size-ы
height[v]	v поддеревосының height-ы

Типтік қателер

DFS-қа parent бермеу
Parent-қа қайта кіріп, infinite recursion алу
dfs(to) алдында dp[v] жаңарту
dp[v] үшін base value ұмыту
dp[v][0] және dp[v][1] шатастыру
Answer max/min керек кезде тек dp[1][1] алу
Үлкен ағашта stack overflow алу

Асимптотика

Задача	Уақыт	Память
Поддерево size	O(n)	O(n)
Independent Set	O(n)	O(n)
Vertex Cover	O(n)	O(n)
Diameter	O(n)	O(n)

Tree DP көбіне O(n), себебі DFS әр вершина мен әр edge-ті бір рет қарайды.

Қысқа Tree DP шаблон

void dfs(int v, int p) {
    // base dp[v]

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        dfs(to, v);

        // update dp[v] using dp[to]
    }
}

Қысқа dp[v][0/1] шаблон

void dfs(int v, int p) {
    dp[v][0] = base0;
    dp[v][1] = base1;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        dfs(to, v);

        dp[v][0] += transition_when_v_not_taken;
        dp[v][1] += transition_when_v_taken;
    }
}