---
# System prepended metadata

title: Centroid Decomposition

---

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

## Centroid

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

![](https://i.imgur.com/Zox7sv7.png)

**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. 
![](https://i.imgur.com/BVq0Tb1.png)

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. 
![](https://i.imgur.com/zTF1zJb.png)

**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.

![](https://i.imgur.com/O2GjGZi.png)
Balandligi 4 bo'lgan centroidlarni topdik.
![](https://i.imgur.com/sCZZzoA.png)
Va nihoyat hamma centroidlarni topib oldik. Quyidagi rasmda ko'k rang bilan ularning  `d[v]` balandligi berilgan.
![](https://i.imgur.com/TqLNJGN.png)

$p[v]$ massiv orqali har bitta centroid qaysi centroid orqali kelinganligini tiklash mumkin.
![](https://i.imgur.com/CSwSNdu.png)


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


Tepadagi daraxtni ildizli daraxt ko'rinishiga keltiramiz
![](https://i.imgur.com/WJUlMRT.png)


**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


```cpp
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)$

```cpp
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.

```cpp

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
