---
disqus: temurbekkhujaev
---
# Centroid Decomposition

## Centroid

**Definition 1.** *Centroid* -- daraxtdagi shunday uchki, o'chirilgandan keyin har qanday komponentadagi uchlar soni $\leq n/2$ bo'ladi.


**Lemma 1.2** Daraxtda kamida bitta centroid bor.

Isbot: Qaysidir ixtiyoriy $v \in V$ uchni olaylik. 2 xil holat bo'lishi mumkin:
1. $v$ -- centroid
2. $v$ ning qaysidir $u$ qo'shnisining komponentasi hajmi $>n/2$

1-holatda centroidni topdik, 2-holatda bundan xulosa qilish mumkinki, centroid $u$ ning komponentasida joylashgan. Tepadagi qadamlarni rekursiv tarzda $u$ uchun ham bajaramiz, va bu qachondir centroidga olib boradi, chunki komponentani hajmi borgan sari kichiklashib boradi.

## Centroid Decomposition tree
Quyidagi rasmda qizil rang bilan centroid va centroidni o'chirgandan keyin hosil bo'ladigan komponentalar ko'rsatilgan.

Centroidni o'chirgandan keyin qolgan har bir komponenta uchun rekursiv tarzda centroidlarni topamiz va topilgan centroidlarni otasi sifatida o'chirilgan ularni bo'lib yuborgan centroidni, ya'ni qizil centroidni eslab ketamiz.

**Definition 1.3** $C(v)$ bu $v$ uch centroid eng baland centroid hisoblangan komponenta.

Bundan oldingi rasmdagi qizil shtrix chiziq orqali 3 ta komponenta ko'rsatilgandi va shularga mos ravishda bu safar balandligi 2 bo'lgan 3 ta centroid topildi va ular topilgan komponentalar ularning $C(v)$ lari hisoblanadi.

Balandligi 4 bo'lgan centroidlarni topdik.
Va nihoyat hamma centroidlarni topib oldik. Quyidagi rasmda ko'k rang bilan ularning `d[v]` balandligi berilgan.

$p[v]$ massiv orqali har bitta centroid qaysi centroid orqali kelinganligini tiklash mumkin.

**Definition 1.4** $p[]$ va $d[]$ massivlari orqali centroid decomposition ifodalanadi

Tepadagi daraxtni ildizli daraxt ko'rinishiga keltiramiz

**Lemma 1.5** Centroid Decomposition daraxti balandligi $\leq log_2(n)$.
Isbot: har bir uroven balandlikdagi centroidlar o'z komponentalarini kamida 2 ga bo'lib yuboradi.

## Realizatsiya

const int N = 200200;
vector<int> g[N];
vector<int> d(N, -1);
vector<int> p(N, -1);

int get_centroid(int v, int parent, int n, int &centroid) { // componentada centroid uchun funksiya
        
        int size = 1; // subtree ni razmeri
        for (auto x:g[v]) { 
                if (x != parent && d[x] == -1) {  
                        size += get_centroid(x, v, n, centroid);
                }
        }
        if (size * 2 >= n && centroid == -1) centroid = v; // agar bu eng pastda joylashgan size * 2 >= n bajariladigan vershina bo'lsa demak bu centroid
        return size;
}

void build(int v, int parent, int depth, int n) {
        int centroid = -1;
        get_centroid(v, -1, n, centroid); // centroidni topamiz 
        if (centroid == -1) centroid = v;
        d[centroid] = depth; 
        p[centroid] = parent;
        for (auto x:g[centroid]) {
                if (d[x] == -1) build(x, centroid, depth + 1, (n + 1) / 2);
        }
}

## Qo'llanilishi

**Lemma 1.6** har qanday $a,b \in V$ uchun, shunaqangi centroid $v$ mavjudki, $v \in$ [$a$ va $b$ orasidagi yo'l], va $a,b \in C(v)$

Isbot: Eng baland centroid $v$ ni olamiz, unda ikki holat bor
1. $a$ va $b$ har xil subtreelarda yotibdi demak $a$ dan $b$ ga yo'l $v$ orqali o'tadi
2. $a$ va $b$ bir xil subtree da yotibdi demak algoritmni rekursiv tarzda shu $a$ va $b$ yotgan komponentada davom ettirish kerak.

$v$ ni topish uchun centroid decomposition daraxtidagi LCA($a$,$b$) ni topish kerak.

Demak har qanday yo'lni $a \rightarrow v \rightarrow b$ ko'rinishda ifodalashimiz mumkin.

### Centroid Decomposition Daraxtida LCAni topish $O(logn)$

int get_lca(int a,int b) {
    while (d[a] > d[b]) a = p[a]; // a ni kamida b ga ko'tarish
    while (d[b] > d[a]) b = p[b]; // b ni kamida a ga ko'tarisrh
    while (a != b) a = p[a], b= p[b]; // a va b ni parallel ko'tarish lcaga borgunicha
    return a;
}

Daraxtning balandligi logarifmik ekanligidan foydalanib buni $O(log (n))$ da shunchaki shunchaki perebor orqali topa oldik. buni keyinchalik $O(log(log (n)))$ yoki $O(1)$ gacha optimizatsiya qilish imkoni bor. (*Binary-lifting*, *Farach-Colton*).

### Yo'ldagi minimumni topish

**Lemma 1.7** $\sum{C(v)} \leq nlog_2(n)$

Har bir $v \in V$ uchun uning $C(V)$ daraxtida har bir $u \in C(v)$ uchlar uchun $v \rightarrow u$ yo'ldagi minimumni preprocessing qilib topib olamiz. Bularni `f[depth[v]][u]` ga saqlab ketsa bo'ladi, chunki har bir $u \in V$, $depth[v]$ balandlikdagi $C(v)$da aynay bir marta uchraydi.

Lemma 1.7 ga ko'ra bunga $O(nlog(n))$ vaqt va xotira ketadi. Keyin har bir $a,b \in V$ uchun, $a \rightarrow b$ yo'ldagi minimum `min(f[depth[v]][a],f[depth[v]][b])` ga teng.

int f[LOG][N];
void pre_calc(int v,int parent, int depth, int cur_min) {
    cur_min = min(cur_min, value[v]);
    f[depth][v] = cur_min; //v depth-- chuqurlikdagi faqat bitta C(v) da uchraydi.
    for (auto x:g[v]) {
        if (x!= parent && depth[x] >= depth[v]) { //x tegishli C(V) bo'lsa
            pre_calc(x, v, depth + 1, cur_min);
        }
    }
}
int get_min(int a, int b) {
    int v = get_lca(a, b);
    return min(f[d[v]][a], f[d[v]][b]);
}

### Uzunligi = L bo'lgan yo'llar ichida max summaligini toping
todo
### Uzunligi L dan R ga cha bo'lgan yo'llar soni
todo
### Eng yaqin bo'yalgan uch
todo
### XOR=0 bo'lgan yo'l
todo
### Yo'ldagi MEX
todo

## Masalalalar

https://codeforces.com/group/mcSSKLGGT5/contest/293496/problem/U
https://codeforces.com/problemset/problem/321/C
IOI 2011 Race masalasi