Heavy-Light Decomposition (HLD): phan tach cay thanh cac chuoi nang (heavy chain) de truy van duong di trong O(log^2 n). Cay 9 dinh, root = 1.
Step 2 / 7
Buoc 1: Tinh kich thuoc cay con (subtree size). sz[1]=9, sz[2]=5, sz[3]=3, sz[5]=3, sz[6]=2. Con nang = con co subtree lon nhat.
Step 3 / 7
Chuoi nang 1: 1 -> 2 -> 5 -> 7. Node 2 la con nang cua 1 (sz=5 > sz[3]=3). Node 5 la con nang cua 2 (sz=3 > sz[4]=1). Node 7 la con nang cua 5 (chon dau tien).
Step 4 / 7
Chuoi nang 2: 3 -> 6 -> 9. Node 3 la con nhe cua 1, bat dau chuoi moi. Node 6 la con nang cua 3 (sz=2 > 0).
Buoc 4: Lam phang cay thanh mang theo thu tu HLD. Chuoi 1: [1,2,5,7], Chuoi 2: [3,6,9], Don: [4], [8]. Moi chuoi la doan lien tiep!
Step 7 / 7
Truy van duong di (vd 4 -> 9): nhay len dau chuoi O(log n) lan, moi lan truy van doan lien tiep tren Segment Tree. Tong O(log^2 n). HLD bien bai toan tren cay thanh bai toan tren doan!