Центроид задаргаа¶

Урьдчилсан нөхцөл мэдлэг: Гүнзгийрүүлэх хайлт (DFS), Хуваа ба ялагтун, Мод.

Оршил¶

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

Гол санаа нь модны центроид-ыг олох замаар түүнийг рекурсивээр задлах явдал юм. Энэ онцгой оройг хасахад мод компонентуудад хуваагдах ба тэдгээр бүр нь анхны модны оройнуудын хамгийн ихдээ хагасыг агуулна. Энэ нь рекурсийн логарифм гүнийг баталгаажуулж, үр ашигтай алгоритмд хүргэдэг.

Центроидын шинж чанар ба тодорхойлолт¶

Эхлээд центроид гэж юу болохыг ойлгоцгооё. Модны центроид гэдэг нь хассаны дараа ямар ч дэд мод $\frac{N}{2}$-ээс олон оройтой байхгүй болох орой юм, энд $N$ нь мод дахь оройн нийт тоо.

$N$ оройтой дурын өгөгдсөн модны хувьд нэг эсвэл хоёр центроид оршино. Хэрэв хоёр центроид байвал тэдгээр нь мөн зэргэлдээ байх ёстой.

Оршин байх ба давтагдашгүй байдал¶

Теорем: Мод бүр дор хаяж нэг центроидтой, хамгийн ихдээ хоёр центроидтой байна. Хэрэв хоёр центроид байвал тэдгээр нь зэргэлдээ байх ёстой.

Баталгаа

Оршин байх: Дурын оройноос эхлээд хамгийн том дэд модтой хүүхэд рүү шилжсээр бай. Ямар ч хүүхэд $\frac{N}{2}$-ээс олон оройтой байхгүй болоход зогс. Энэ үед одоогийн орой $v$ нь центроид болно, учир нь (1) ямар ч хүүхдийн дэд мод $\frac{N}{2}$-ээс олон орой агуулахгүй (зогсох нөхцөлөөр) (2) "эцгийн тал" ($v$ хүүхэд байхад $v$-ийн дэд модноос бусад бүх орой) хамгийн ихдээ $\frac{N}{2}$ орой агуулна (эс бөгөөс бид эцгээс $v$ рүү шилжихгүй байсан).

Энэ процесс үргэлж дуусдагийг харахад амархан бөгөөд ингэснээр дор хаяж нэг центроид оршин байгааг батална.

Давтагдашгүй байдал: Хоёр центроид $u$ ба $v$ байна гэж үзье. Тэдгээрийн хоорондох замыг авч үзье. Бид $u$-г хасахад орой $v$ хамгийн ихдээ $\frac{N}{2}$ оройтой компонентод байх ёстой. Үүнтэй адилаар бид $v$-г хасахад орой $u$ хамгийн ихдээ $\frac{N}{2}$ оройтой компонентод байх ёстой. Энэ нь зөвхөн $u$ ба $v$ зэргэлдээ бол л боломжтой; эс бөгөөс аль нэгийг нь хасах нь нөгөөг $\frac{N}{2}$-ээс олон оройтой компонентод оруулна. Энэ нь хоёр центроид хоёулаа хамгийн ихдээ $\frac{N}{2}$ оройтой компонентод байна гэсэн бидний анхны мэдэгдэлтэй зөрчилдөнө. Түүнээс гадна хэрэв хоёр центроид оршвол тэдгээр нь модыг тус бүр яг $\frac{N}{2}$ оройтой хоёр компонентод хуваах ёстой бөгөөд энэ нь зөвхөн $N$ тэгш үед л боломжтой.

Центроид задаргааны шинж чанар ба тодорхойлолт¶

Модыг "задлах" гэдэг нь үндсэндээ центроидуудыг рекурсивээр олж, центроидын компонентууд дээр үндэслэн модыг дэд модуудад хуваахыг хэлнэ. Модыг ийнхүү компонентууд болгон рекурсивээр задлах нь давтагдашгүй шинж чанаруудын багцыг үүсгэнэ:

Задаргааны гүн: Түвшин бүр компонентын хэмжээг дор хаяж хоёр дахин багасгадаг тул гүн нь $O(\log N)$ байна.
Замын бүрхэлт: Мод дахь зам бүр задаргаа дахь ямар нэг компонентын центроидоор дайран өнгөрнө.

Задаргааны гүн¶

Теорем: Дурын өгөгдсөн мод дээр центроид задаргаа ашиглах үеийн гүн буюу алхмын тоо нь $O(\log N)$ байна.

Баталгаа

Анхны мод дахь дурын орой $v$-г авч үзье. Задаргааны процессын явцад $v$ хэдэн удаа компонентын хэсэг байж болохыг бид хянана.

Эхний түвшинд $v$ нь $N$ хэмжээтэй компонентод байна. Бид энэ компонентын центроидыг хасахад $v$ хамгийн ихдээ $\frac{N}{2}$ хэмжээтэй компонентод очно (тэнцвэрийн шинж чанараар).

Хоёр дахь түвшинд $v$ нь хамгийн ихдээ $\frac{N}{2}$ хэмжээтэй компонентод байна. Энэ компонентын центроидыг хасах нь $v$-г хамгийн ихдээ $\frac{N}{4}$ хэмжээтэй компонентод оруулна.

Энэ хэв маягийг үргэлжлүүлбэл $k$ дахь түвшинд $v$ нь хамгийн ихдээ $\frac{N}{2^{k-1}}$ хэмжээтэй компонентод байна.

Компонентын хэмжээ 1 хүрэхэд задаргаа зогсоно. Энэ нь $\frac{N}{2^{k-1}} \leq 1$ үед тохиолдох ба эндээс бид $k \leq \log_2 N + 1$ авна.

Тиймээс центроид задаргааны модны хамгийн их гүн нь $O(\log N)$ юм.

Үр дагавар: Орой бүр задаргааны хамгийн ихдээ $O(\log N)$ түвшинд оролцох ба бид түвшин бүрд орой бүрийг нэг удаа боловсруулдаг тул центроид задаргаа ашигладаг алгоритмууд ихэвчлэн түвшин бүрд орой бүрд хийгдэх ажлаар үржүүлсэн $O(\log N)$ time complexity үржигдэхүүнтэй байдаг.

Замын бүрхэлт¶

Теорем: Анхны мод дахь зам бүр задаргаа дахь ямар нэг компонентын центроидоор дайран өнгөрнө.

Баталгаа

Анхны мод дахь орой $u$-ээс орой $v$ хүрэх дурын зам $P$-г авч үзье. Энэ зам задаргааны процессын явцад сонгогдсон дор хаяж нэг центроидоор дайран өнгөрдгийг бид харуулах хэрэгтэй.

Бид үүнийг задаргааны процесс дээрх индукцээр батална.

Суурь тохиолдол: Задаргааны эхний түвшинд бид бүхэл модны центроид $c_1$-г сонгоно. Хэрэв зам $P$ нь $c_1$-ээр дайран өнгөрвөл бид дууслаа.

Индукцийн тохиолдол: Зам $P$ нь $c_1$-ээр дайран өнгөрөхгүй гэж үзье. Бид $c_1$-г хасахад мод олон компонентод хуваагдана. $P$ нь холбоост зам тул $c_1$-г хассаны дараа $u$ ба $v$ хоёул ижил компонент $C$-д орших ёстой (эс бөгөөс $P$ тэдгээрийг холбохын тулд $c_1$-ээр дайран өнгөрөх ёстой болох ба энэ нь бидний таамаглалтай зөрчилдөнө).

Одоо бид компонент $C$-г рекурсивээр задална. Компонент $C$-д хэрэглэсэн индукцийн таамаглалаар зам $P$ (энэ нь бүхэлдээ $C$-д агуулагдана) нь $C$-ийн задаргаа дахь ямар нэг компонентын центроидоор дайран өнгөрөх ёстой.

Энэ процесс $P$ дайран өнгөрөх центроидыг олох хүртэл үргэлжилнэ. Процесс заавал дуусах ёстой, учир нь түвшин бүрд $P$-г агуулсан компонент чанд утгаараа багасах ба (тэнцвэрийн шинж чанараар) эцэст нь ганц ирмэг эсвэл орой болж буурна.

Үр дагавар: Энэ шинж чанар нь центроид задаргааны алгоритмуудын зөв байдлын үндэс суурь юм. Энэ нь бид центроид бүрээр дайрах бүх замыг боловсруулахад задаргааны ямар нэг түвшинд мод дахь боломжит бүх замыг яг нэг удаа бүрхэхийг баталгаажуулна. Иймээс л центроид задаргаа замтай холбоотой бодлогыг үр ашигтай бодож чадна: зам бүрийг центроидтой анх тулгарах түвшинд яг нэг удаа авч үзнэ.

Центроид олох¶

Модны центроидыг үр ашигтай олохын тулд:

Гүнзгийрүүлэх хайлт (DFS) ашиглан бүх оройн дэд модны хэмжээг тооцоол
Дурын оройноос эхэл
Дэд мод нь $\frac{N}{2}$-ээс олон орой агуулах хүүхэд $v$-г ол
$v$ рүү шилжиж, 3-р алхмыг давт
Хэрэв ийм хүүхэд байхгүй бол одоогийн орой нь центроид юм

Time complexity: $O(N)$.

Space complexity: $O(N)$.

Алгоритмын тайлбар¶

Центроид задаргаа ашиглах үед ерөнхий урсгал дараах байдлаар ажиллана:

Одоогийн мод/компонентын центроидыг ол
Энэ центроидоор дайран өнгөрөх бүх замыг боловсруулж, хүссэн тооцооллоо хий
Центроидыг хас (түүнийг ашигласан гэж тэмдэглэ)
Үүссэн дэд мод бүрийг рекурсивээр задал

Энэ нь центроид мод үүсгэнэ. Энэ мод дахь зангилаа бүр задаргааны ямар нэг үе шатны центроидыг илэрхийлнэ. Энэ нь центроидын (дурын өгөгдсөн зангилааны) эцэг нь түүнийг агуулсан илүү том компонентод олдсон центроид гэсэн үг. Энэ модны өндөр өмнө баталсанчлан $O(\log N)$ байна.

Жишээ нь дээрх зурагт бидэнд центроид мод байна. Модны түвшин бүр дэх зангилаа бүр нь тэр компонентын центроид юм (жишээ нь үндэс нь бүхэл модны центроид, үндсийн хамгийн зүүн хүүхэд нь үндсийн хамгийн зүүн дэд модны центроид гэх мэт).

Implementation¶

Here's an implementation of centroid decomposition solving a specific problem: counting all paths in the tree with length exactly $K$.

In this problem, we're given a tree with $N$ vertices and need to count how many paths have exactly $K$ edges. A path is defined by two distinct vertices.

const int MAXN = 1e5;
vector<int> adj[MAXN];
bool removed[MAXN];
int subtree_size[MAXN];
int K;  // Target path length
long long answer = 0;  // Count of paths with length K

int get_subtree_size(int v, int p = -1) {
    subtree_size[v] = 1;
    for (int u : adj[v]) {
        if (u == p || removed[u]) continue;
        subtree_size[v] += get_subtree_size(u, v);
    }
    return subtree_size[v];
}

int get_centroid(int v, int tree_size, int p = -1) {
    for (int u : adj[v]) {
        if (u == p || removed[u]) continue;
        if (subtree_size[u] * 2 > tree_size)
            return get_centroid(u, tree_size, v);
    }
    return v;
}

void get_distances(int v, int p, int dist, vector<int>& distances) {
    if (dist > K) return;
    distances.push_back(dist);
    for (int u : adj[v]) {
        if (u == p || removed[u]) continue;
        get_distances(u, v, dist + 1, distances);
    }
}

void process_centroid(int centroid) {
    unordered_map<int, int> all_distances;
    all_distances[0] = 1;

    for (int u : adj[centroid]) {
        if (removed[u])
            continue;

        vector<int> current_distances;
        get_distances(u, centroid, 1, current_distances);

        for (int d : current_distances) {
            if (K - d >= 0) {
                answer += (all_distances[K - d] ? all_distances[K - d] : 0);
            }
        }

        for (int d : current_distances) {
            if (all_distances.find(d) == all_distances.end())
                all_distances[d] = 0;
            all_distances[d]++;
        }
    }
}

void decompose(int v) {
    int tree_size = get_subtree_size(v);
    int centroid = get_centroid(v, tree_size);

    process_centroid(centroid);

    removed[centroid] = true;

    for (int u : adj[centroid]) {
        if (!removed[u]) {
            decompose(u);
        }
    }
}

This template can be adapted to solve different problems using centroid decomposition. In this specific case, it solves the problem of counting all paths of length $K$. The strategy is: for each centroid, count paths passing through it by finding pairs of vertices in different subtrees at distances $d_1$ and $d_2$ their sum is $K$ (i.e. a path passing through the centroid consists of a vertex in one subtree at distance $d_1$ from the centroid and a vertex in another subtree at distance $d_2$ where $d_1 + d_2 = K$). For each distance $d$ in the current subtree, the code counts how many vertices are at distance $K - d$ in previous subtrees. The optimization skips distances beyond $K$ to avoid unnecessary recursion.

Building the Centroid Tree¶

If you need to build an explicit centroid tree structure (useful for answering queries):

int centroid_parent[MAXN];

int decompose(int v, int p = -1) {
    int tree_size = get_subtree_size(v);
    int centroid = get_centroid(v, tree_size);

    centroid_parent[centroid] = p;
    removed[centroid] = true;

    for (int u : adj[centroid]) {
        if (!removed[u]) {
            decompose(u, centroid);
        }
    }

    return centroid;
}

Дасгал бодлогууд¶

CSES - Finding a Centroid [difficulty: easy]
CSES - Fixed-Length Paths II [difficulty: easy]
Codeforces - Xenia and Tree [difficulty: medium]
Codeforces - Digit Tree [difficulty: medium]
OJ - Race [difficulty: medium]
SPOJ - QTREE5 [difficulty: hard]