DP дар дарахт (Tree DP) - Course 4

Module 1: Trie

БОР

Module 2: Sparse Table

Ҷадвали пароканда

Module 3: Segment Tree

Дарахти порчаҳо
Максимумии суммаи зерпорча дар порчаи додашуда

Module 4: Segment Tree Lazy propagation

Дарахти сегментӣ бо паҳнкунии танбалона

Module 5: More on trees

Эйлер тартиби боздиди қуллаҳо
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$ бошад. Қуллаҳо якто-якто илова мешаванд.

Иддао:

Ду қуллаи $O(n)$ вуҷуд доранд, ки барои ҳар қуллаи $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);
    }
}