Centroid Decomposition

Centroid Decomposition เป็นเทคนิค divide and conquer บน tree โดยแบ่ง tree ตาม centroid (node ที่เมื่อลบออกแล้ว ทุก subtree มีขนาดไม่เกิน $n/2$)

Centroid คืออะไร?

Centroid ของ tree คือ node ที่เมื่อลบออกแล้ว ทุก connected component ที่เหลือมีขนาด $\leq n/2$

ทุก tree มี centroid อย่างน้อย 1 ตัว (และมากสุด 2 ตัว)

หา Centroid

class CentroidDecomposition {
    int n;
    vector<vector<int>> adj;
    vector<bool> removed;
    vector<int> subtreeSize;
    
    int calcSize(int u, int p) {
        subtreeSize[u] = 1;
        for (int v : adj[u]) {
            if (v != p && !removed[v]) {
                subtreeSize[u] += calcSize(v, u);
            }
        }
        return subtreeSize[u];
    }
    
    int findCentroid(int u, int p, int treeSize) {
        for (int v : adj[u]) {
            if (v != p && !removed[v] && subtreeSize[v] > treeSize / 2) {
                return findCentroid(v, u, treeSize);
            }
        }
        return u;
    }
    
public:
    vector<int> centroidParent;  // parent in centroid tree
    
    CentroidDecomposition(int n) : n(n), adj(n), removed(n, false), 
                                    subtreeSize(n), centroidParent(n, -1) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    int decompose(int u, int p = -1) {
        int treeSize = calcSize(u, -1);
        int centroid = findCentroid(u, -1, treeSize);
        
        removed[centroid] = true;
        centroidParent[centroid] = p;
        
        for (int v : adj[centroid]) {
            if (!removed[v]) {
                decompose(v, centroid);
            }
        }
        
        return centroid;
    }
};

Centroid Tree

ผลลัพธ์ของ decomposition คือ Centroid Tree ที่มีความสูง $O(\log n)$

Original Tree:          Centroid Tree:
    1                       3
   /|\                     /|\
  2 3 4                   1 4 6
 /   / \                 /   |
5   6   7               2    7
                        |
                        5

ประยุกต์ใช้งาน

1. Count Paths of Length K

นับจำนวน paths ที่มีความยาว exactly $k$

int countPathsOfLengthK(int k) {
    int total = 0;
    
    function<void(int)> solve = [&](int u) {
        int treeSize = calcSize(u, -1);
        int centroid = findCentroid(u, -1, treeSize);
        removed[centroid] = true;
        
        // Count paths through centroid
        map<int, int> cnt;  // cnt[d] = number of nodes at distance d from centroid
        cnt[0] = 1;
        
        for (int v : adj[centroid]) {
            if (removed[v]) continue;
            
            // Collect distances from this subtree
            vector<int> distances;
            function<void(int, int, int)> collect = [&](int node, int parent, int dist) {
                distances.push_back(dist);
                for (int next : adj[node]) {
                    if (next != parent && !removed[next]) {
                        collect(next, node, dist + 1);
                    }
                }
            };
            collect(v, centroid, 1);
            
            // Count paths using previous subtrees
            for (int d : distances) {
                if (cnt.count(k - d)) {
                    total += cnt[k - d];
                }
            }
            
            // Add distances to cnt
            for (int d : distances) {
                cnt[d]++;
            }
        }
        
        // Recurse on subtrees
        for (int v : adj[centroid]) {
            if (!removed[v]) {
                solve(v);
            }
        }
    };
    
    solve(0);
    return total;
}

2. Distance to Closest Marked Node

หาระยะทางจาก node ใดๆ ไปยัง marked node ที่ใกล้ที่สุด

class ClosestMarked {
    CentroidDecomposition cd;
    vector<int> minDist;  // min distance to marked node through each centroid
    
    int dist(int u, int v) {
        // Compute actual distance in original tree
        // (using BFS or precomputed LCA)
    }
    
public:
    ClosestMarked(int n) : cd(n), minDist(n, INT_MAX) {}
    
    void mark(int u) {
        int cur = u;
        while (cur != -1) {
            minDist[cur] = min(minDist[cur], dist(u, cur));
            cur = cd.centroidParent[cur];
        }
    }
    
    int query(int u) {
        int ans = INT_MAX;
        int cur = u;
        while (cur != -1) {
            if (minDist[cur] != INT_MAX) {
                ans = min(ans, dist(u, cur) + minDist[cur]);
            }
            cur = cd.centroidParent[cur];
        }
        return ans;
    }
};

3. Path Query with Condition

หา path ที่ max edge weight น้อยที่สุด

struct PathQuery {
    CentroidDecomposition cd;
    vector<map<int, int>> nodeInfo;  // nodeInfo[c][dist] = min max_edge to reach distance dist from c
    
    void preprocess() {
        // Build decomposition
        cd.decompose(0);
        
        // For each centroid, precompute paths
        for (int c = 0; c < n; c++) {
            // BFS/DFS from c to compute distances and max edges
        }
    }
    
    int query(int u, int v) {
        // Find paths through each common centroid ancestor
        // Return best answer
    }
};

Complexity Analysis

Time Complexity

• Build Centroid Tree: $O(n \log n)$

  • หา centroid: $O(n)$
  • Depth ของ centroid tree: $O(\log n)$
  • Total: $O(n \log n)$

• Query ผ่าน Centroid Tree: $O(\log n)$ per ancestor

  • มี $O(\log n)$ ancestors
  • Total per query: $O(\log n)$ ถึง $O(\log^2 n)$ ขึ้นกับ work per ancestor

Space Complexity

• $O(n)$ สำหรับ centroid tree structure
• เพิ่มเติมขึ้นกับ data structures ที่ใช้

เปรียบเทียบกับ HLD

Aspect	Centroid Decomposition	HLD
ประเภทปัญหา	Path counting, closest marked	Path sum/max queries
การ update	ง่าย (update ผ่าน ancestors)	ต้องใช้ segment tree
Implementation	ง่ายกว่า	ซับซ้อนกว่า
Tree depth	$O(\log n)$	$O(\log n)$ chains

Tips

1. Centroid tree มี height O(log n) - guarantees efficiency
2. ใช้ divide and conquer - แก้ปัญหาที่ต้องนับ/หา paths
3. Mark nodes technique - มีประโยชน์มากสำหรับ dynamic queries
4. Combine กับ data structures เช่น BIT, Segment Tree ตาม need