{"title":"Centroid Decomposition","description":"","content":"You have a tree with 100,000 nodes, and someone asks you to answer thousands of distance queries between arbitrary pairs of nodes. Or maybe you need to find the closest \"marked\" node to a given node, and marks keep getting added over time. A naive DFS for each query gives you O(n) per query, which is far too slow when both the tree and the number of queries are large.\n\nCentroid decomposition is the technique that turns these O(n)-per-query problems into O(log n) per query. It works by recursively finding the \"center\" of the tree, using it to process all paths that pass through that center, and then decomposing the remaining subtrees the same way. The result is a new tree, the centroid tree, with only O(log n) depth, and this shallow structure is what makes fast queries possible.\n\n---\n\n# Why Centroid Decomposition Matters\n\nTree path queries come up constantly in competitive programming and occasionally in interviews at companies that test advanced algorithmic thinking. The challenge is that trees do not have the nice linear structure of arrays, where you can apply prefix sums or segment trees directly. Paths in trees can twist and turn, and two nodes that are far apart in the tree might have a path that passes through many intermediate nodes.\n\nCentroid decomposition gives you a systematic way to handle any problem that involves processing all paths in a tree, or answering queries about paths efficiently. Here is where it shows up:\n\n- **Distance queries.** Given a tree with weighted edges, answer \"what is the distance between nodes u and v?\" for many pairs. With centroid decomposition, you can precompute distances to answer each query in O(log n).\n- **Closest marked node.** Nodes get marked over time, and you need to find the closest marked node to a query node. Centroid decomposition handles this with O(log n) per update and query.\n- **Counting paths with a property.** How many paths in the tree have total weight exactly k? Or at most k? Centroid decomposition lets you enumerate all paths efficiently by processing paths through each centroid.\n- **Competitive programming.** Problems on Codeforces, SPOJ, and USACO regularly require centroid decomposition. It is one of those techniques that, once you learn it, unlocks a whole category of tree problems.\n\n---\n\n# The Core Idea\n\n### The Problem\n\nSuppose you have an unrooted tree with n nodes and you want to count how many paths have a total weight equal to some target k. The brute force approach is to run a DFS from every node, exploring all possible paths. That is O(n^2) in the worst case, since each DFS can visit up to n nodes and you start from each of the n nodes.\n\nFor a single query like \"what is the distance from u to v?\", you can answer it in O(n) with a single BFS or DFS. But if you have q queries, that becomes O(n * q), which is too slow when both n and q are around 100,000.\n\nWe need a way to preprocess the tree so that each query takes much less than O(n).\n\n### The Key Insight\n\nHere is the central observation: **every tree has a centroid**, a node whose removal splits the tree into components where no component has more than n/2 nodes. This is a powerful guarantee. It means that if you pick the centroid and remove it, every remaining subtree is at most half the size of the original tree.\n\nWhy does this matter? Because you can use a divide-and-conquer strategy:\n\n1. Find the centroid of the current tree.\n2. Process all paths that pass through this centroid.\n3. Remove the centroid and recurse on each remaining subtree.\n\nSince each subtree is at most half the size, the recursion depth is O(log n). And at each level of recursion, the total work across all subtrees is O(n) (because the subtrees partition the nodes). This gives O(n log n) total work for the entire decomposition.\n\nThe result of this recursive process is a new tree called the **centroid tree**. In the centroid tree, the centroid of the original tree is the root, and its children are the centroids of the subtrees that remained after removing it. This centroid tree has depth O(log n), and it has a remarkable property: for any two nodes u and v in the original tree, their path passes through their lowest common ancestor (LCA) in the centroid tree.\n\n### The Analogy\n\nThink of it like setting up distribution hubs for a country. If you want to efficiently route packages between any two cities, you find the geographic center of the country and build a hub there. Every package route can go through this central hub. Then for each region that remains, you find its center and build a regional hub. You keep going until every small area has its own local hub. The hierarchy of hubs (national, regional, local) has only a few levels because each level halves the area. Any package route only needs to go up and down through O(log n) hubs.\n\n### Visual Overview\n\nThe following diagram shows the high-level idea. You start with a tree, find its centroid, remove it, and recurse on the pieces. The centroids form a new tree with logarithmic depth.\n\n\n```mermaid\nflowchart TD\n subgraph Original[\"Original Tree\"]\n A[\"Find Centroid\"]:::primary\n end\n\n subgraph Step1[\"Step 1: Remove Centroid\"]\n B[\"Subtree 1
(at most n/2)\"]:::orange\n C[\"Subtree 2
(at most n/2)\"]:::orange\n D[\"Subtree 3
(at most n/2)\"]:::orange\n end\n\n subgraph Step2[\"Step 2: Recurse\"]\n E[\"Find centroid
of each subtree\"]:::teal\n end\n\n subgraph Result[\"Centroid Tree\"]\n F[\"Depth O(log n)\"]:::green\n end\n\n Original --> Step1\n Step1 --> Step2\n Step2 --> Result\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n# How It Works\n\n### Step 1: Finding the Centroid\n\nTo find the centroid of a tree (or subtree) with n nodes, you need to:\n\n1. **Compute subtree sizes.** Root the tree at any node and run a DFS to compute the size of every subtree.\n2. **Find the node where the largest remaining component has size at most n/2.** When you \"remove\" a node v from a tree of size n, the remaining components are: each of v's children's subtrees, plus the \"parent side\" (which has size n - subtreeSize[v]). The largest of these components must be at most n/2 for v to be the centroid.\n\nHere is the key formula. For a node v with children c1, c2, ..., ck in the rooted tree:\n\n- The sizes of the child subtrees are subtreeSize[c1], subtreeSize[c2], ..., subtreeSize[ck].\n- The size of the \"upward\" component is treeSize - subtreeSize[v].\n- The maximum component size when v is removed is: max(subtreeSize[c1], subtreeSize[c2], ..., subtreeSize[ck], treeSize - subtreeSize[v]).\n- v is the centroid if this maximum is at most treeSize / 2.\n\nEvery tree has at least one centroid (and at most two, in which case they are adjacent). We only need one, so we pick the first one we find.\n\n\n```mermaid\nflowchart TD\n A[\"Root tree at
any node\"]:::primary --> B[\"DFS to compute
subtree sizes\"]:::teal\n B --> C[\"For each node v,
compute max component
if v is removed\"]:::orange\n C --> D{\"Max component
at most n/2?\"}:::primary\n D -->|\"Yes\"| E[\"v is the centroid\"]:::green\n D -->|\"No\"| F[\"Try next node\"]:::red\n F --> C\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n### Step 2: Process Paths Through the Centroid\n\nOnce you have the centroid, you know that every path in the current tree either:\n\n- Passes through the centroid, or\n- Is entirely contained within one of the subtrees that remain after removing the centroid.\n\nPaths in the second category will be handled by the recursive calls. So at this level, you only need to process paths that pass through the centroid. This is the \"conquer\" step and it depends on the specific problem you are solving. For distance queries, you might store the distance from the centroid to every node in the current tree. For counting paths of weight k, you might use a hash map to count complementary distances.\n\n### Step 3: Remove the Centroid and Recurse\n\nAfter processing, you mark the centroid as \"removed\" (so future DFS calls skip it) and recurse on each remaining connected component. Each component is a subtree rooted at one of the centroid's neighbors (in the current tree), and each has size at most n/2.\n\nThe centroid found in each recursive call becomes a child of the current centroid in the centroid tree. This builds the centroid tree implicitly as the recursion proceeds.\n\n### The Complete Decomposition Process\n\n\n```mermaid\nflowchart TD\n A[\"decompose(tree)\"]:::primary\n A --> B[\"Compute subtree sizes\"]:::teal\n B --> C[\"Find centroid c\"]:::teal\n C --> D[\"Process all paths
through c\"]:::orange\n D --> E[\"Mark c as removed\"]:::red\n E --> F[\"For each neighbor
subtree of c\"]:::primary\n F --> G[\"decompose(subtree)\"]:::teal\n G --> H[\"Set c as parent
of subtree's centroid
in centroid tree\"]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n---\n\n# Example Walkthrough\n\nLet us work through a concrete example with a tree of 7 nodes. The tree looks like this:\n\n\n```shell\n1\n / \\\n 2 3\n / \\ \\\n 4 5 6\n |\n 7\n```\n\n\nEdges: (1,2), (1,3), (2,4), (2,5), (3,6), (5,7). All edges have weight 1 for simplicity.\n\n### Round 1: Finding the Centroid of the Full Tree\n\nThe tree has 7 nodes. We need a node whose removal leaves no component larger than 7/2 = 3.\n\nFirst, root the tree at node 1 and compute subtree sizes:\n\n\n```shell\nsubtreeSize[4] = 1\nsubtreeSize[7] = 1\nsubtreeSize[5] = 2 (5 and 7)\nsubtreeSize[2] = 4 (2, 4, 5, 7)\nsubtreeSize[6] = 1\nsubtreeSize[3] = 2 (3 and 6)\nsubtreeSize[1] = 7 (all nodes)\n```\n\n\nNow check each node. When we remove a node from a tree of size 7, the components are its child subtrees plus the \"upward\" component.\n\n\n| Node | Child subtree sizes | Upward component | Max component |\n|------|-------------------|------------------|---------------|\n| 1 | 4, 2 | 0 | 4 |\n| 2 | 1, 2 | 3 | 3 |\n| 3 | 1 | 5 | 5 |\n| 4 | (none) | 6 | 6 |\n| 5 | 1 | 5 | 5 |\n| 6 | (none) | 6 | 6 |\n| 7 | (none) | 6 | 6 |\n\n\nNode 2 has a max component size of 3, which is at most 7/2 = 3.5. So **node 2 is the centroid**.\n\n### Round 1: Removing Node 2\n\nAfter removing node 2, three components remain:\n\n- Component A: {4} (the subtree rooted at child 4)\n- Component B: {5, 7} (the subtree rooted at child 5)\n- Component C: {1, 3, 6} (the \"upward\" component through node 1)\n\n\n```mermaid\nflowchart LR\n subgraph CentroidTree[\"Centroid Tree (so far)\"]\n CT2[\"2\"]:::primary\n end\n\n subgraph CompA[\"Component A\"]\n N4[\"4\"]:::orange\n end\n\n subgraph CompB[\"Component B\"]\n N5[\"5\"]:::orange --> N7[\"7\"]:::orange\n end\n\n subgraph CompC[\"Component C\"]\n N1[\"1\"]:::teal --> N3[\"3\"]:::teal\n N3 --> N6[\"6\"]:::teal\n end\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n### Round 2: Recurse on Each Component\n\n**Component A: {4}** has a single node. Node 4 is trivially its own centroid. It becomes a child of node 2 in the centroid tree.\n\n**Component B: {5, 7}** has 2 nodes. Node 5 is the centroid (removing it leaves {7}, which has size 1 <= 2/2 = 1). Node 5 becomes a child of node 2. After removing node 5, we recurse on {7}. Node 7 becomes a child of node 5.\n\n**Component C: {1, 3, 6}** has 3 nodes. Let us check:\n\n- Remove node 1: components are {3, 6}. Max size = 2 > 3/2 = 1.5.\n- Remove node 3: components are {1} and {6}. Max size = 1 <= 1.5.\n\nNode 3 is the centroid. It becomes a child of node 2. After removing node 3, components are {1} and {6}. Each is a single node and becomes a child of node 3.\n\n### Final Centroid Tree\n\n\n```mermaid\nflowchart TD\n C2[\"2\"]:::primary\n C2 --> C4[\"4\"]:::orange\n C2 --> C5[\"5\"]:::orange\n C2 --> C3[\"3\"]:::teal\n C5 --> C7[\"7\"]:::green\n C3 --> C1[\"1\"]:::green\n C3 --> C6[\"6\"]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nNotice the depth is only 3 (for 7 nodes). The original tree had depth 4 (path 1-2-5-7). The centroid tree is shallower because every split is balanced.\n\n**Key property to verify:** Consider the path from node 7 to node 6 in the original tree. That path is 7-5-2-1-3-6. In the centroid tree, the LCA of nodes 7 and 6 is node 2 (since 7 is under 5, which is under 2, and 6 is under 3, which is under 2). The original path does indeed pass through node 2. This is not a coincidence. Every path in the original tree passes through the LCA of its endpoints in the centroid tree.\n\n---\n\n# Implementation\n\nHere is a complete implementation of centroid decomposition with a distance query application. The code builds the centroid tree, precomputes distances from each node to all its ancestors in the centroid tree, and then answers distance queries by checking the LCA in the centroid tree.\n\n\n```java\nimport java.util.*;\n\nclass CentroidDecomposition {\n private List[] adj; // adj[u] = list of {v, weight}\n private int[] subtreeSize;\n private boolean[] removed;\n private int[] centroidParent;\n private long[][] distToAncestor; // distToAncestor[node][level]\n private int[] depth; // depth of each node in centroid tree\n private int n;\n\n public CentroidDecomposition(int n) {\n this.n = n;\n adj = new ArrayList[n + 1];\n for (int i = 0; i <= n; i++) {\n adj[i] = new ArrayList<>();\n }\n subtreeSize = new int[n + 1];\n removed = new boolean[n + 1];\n centroidParent = new int[n + 1];\n depth = new int[n + 1];\n // O(log n) ancestors at most\n int maxDepth = (int) (Math.log(n) / Math.log(2)) + 2;\n distToAncestor = new long[n + 1][maxDepth + 1];\n }\n\n public void addEdge(int u, int v, int w) {\n adj[u].add(new int[]{v, w});\n adj[v].add(new int[]{u, w});\n }\n\n // Compute subtree sizes rooted at 'node', skipping removed nodes\n private int computeSize(int node, int parent) {\n subtreeSize[node] = 1;\n for (int[] edge : adj[node]) {\n int next = edge[0];\n if (next != parent && !removed[next]) {\n subtreeSize[node] += computeSize(next, node);\n }\n }\n return subtreeSize[node];\n }\n\n // Find centroid of the subtree rooted at 'node'\n private int findCentroid(int node, int parent, int treeSize) {\n for (int[] edge : adj[node]) {\n int next = edge[0];\n if (next != parent && !removed[next]) {\n // If this child's subtree has more than half the nodes,\n // the centroid must be in that subtree\n if (subtreeSize[next] > treeSize / 2) {\n return findCentroid(next, node, treeSize);\n }\n }\n }\n // Check if current node qualifies\n // The \"upward\" component is treeSize - subtreeSize[node],\n // but after the loop above, no child subtree exceeds treeSize/2.\n // So the only component that could exceed is the upward one.\n // If treeSize - subtreeSize[node] <= treeSize/2, node is centroid.\n // But actually, the loop guarantees we descended into large subtrees.\n // The current node is the centroid.\n return node;\n }\n\n // Store distances from 'centroid' (at given depth) to all nodes in its subtree\n private void computeDistances(int node, int parent, long dist, int centroidDepth) {\n distToAncestor[node][centroidDepth] = dist;\n for (int[] edge : adj[node]) {\n int next = edge[0];\n int weight = edge[1];\n if (next != parent && !removed[next]) {\n computeDistances(next, node, dist + weight, centroidDepth);\n }\n }\n }\n\n // Build centroid decomposition starting from 'node'\n public void build(int node, int parent, int d) {\n int treeSize = computeSize(node, -1);\n int centroid = findCentroid(node, -1, treeSize);\n\n removed[centroid] = true;\n centroidParent[centroid] = parent;\n depth[centroid] = d;\n\n // Store distance from centroid to itself\n distToAncestor[centroid][d] = 0;\n // Compute distances from centroid to all nodes in current subtree\n for (int[] edge : adj[centroid]) {\n int next = edge[0];\n int weight = edge[1];\n if (!removed[next]) {\n computeDistances(next, centroid, weight, d);\n }\n }\n\n // Recurse on each remaining subtree\n for (int[] edge : adj[centroid]) {\n int next = edge[0];\n if (!removed[next]) {\n build(next, centroid, d + 1);\n }\n }\n }\n\n // Query distance between u and v using centroid tree\n public long query(int u, int v) {\n long minDist = Long.MAX_VALUE;\n // Walk up from u and v to find their LCA in centroid tree\n // For every ancestor c of both u and v in the centroid tree,\n // dist(u, v) through c = dist(u, c) + dist(v, c)\n int a = u, b = v;\n // Check all common ancestors\n // The LCA gives the exact distance, but we check all ancestors\n // and take the minimum (they all give valid upper bounds,\n // and the LCA gives the true distance)\n for (int d = Math.min(depth[u], depth[v]); d >= 0; d--) {\n // Both u and v have an ancestor at depth d\n if (distToAncestor[u][d] + distToAncestor[v][d] < minDist) {\n minDist = distToAncestor[u][d] + distToAncestor[v][d];\n }\n }\n return minDist;\n }\n\n public static void main(String[] args) {\n // Example tree:\n // 1\n // / \\\n // 2 3\n // / \\ \\\n // 4 5 6\n // |\n // 7\n int n = 7;\n CentroidDecomposition cd = new CentroidDecomposition(n);\n cd.addEdge(1, 2, 1);\n cd.addEdge(1, 3, 1);\n cd.addEdge(2, 4, 1);\n cd.addEdge(2, 5, 1);\n cd.addEdge(3, 6, 1);\n cd.addEdge(5, 7, 1);\n\n cd.build(1, 0, 0);\n\n // Distance from 4 to 6: path is 4-2-1-3-6, distance = 4\n System.out.println(\"dist(4,6) = \" + cd.query(4, 6));\n // Distance from 7 to 3: path is 7-5-2-1-3, distance = 4\n System.out.println(\"dist(7,3) = \" + cd.query(7, 3));\n // Distance from 4 to 7: path is 4-2-5-7, distance = 3\n System.out.println(\"dist(4,7) = \" + cd.query(4, 7));\n }\n}\n```\n\n```python\nimport sys\nfrom math import log2\nfrom collections import defaultdict\n\nsys.setrecursionlimit(300000)\n\nclass CentroidDecomposition:\n def __init__(self, n):\n self.n = n\n self.adj = defaultdict(list) # adj[u] = [(v, weight), ...]\n self.subtree_size = [0] * (n + 1)\n self.removed = [False] * (n + 1)\n self.centroid_parent = [0] * (n + 1)\n self.depth = [0] * (n + 1)\n max_depth = int(log2(n)) + 2 if n > 0 else 1\n # dist_to_ancestor[node][level] = distance to ancestor at that level\n self.dist_to_ancestor = [[0] * (max_depth + 1) for _ in range(n + 1)]\n\n def add_edge(self, u, v, w):\n self.adj[u].append((v, w))\n self.adj[v].append((u, w))\n\n def _compute_size(self, node, parent):\n \"\"\"Compute subtree sizes, skipping removed nodes.\"\"\"\n self.subtree_size[node] = 1\n for next_node, _ in self.adj[node]:\n if next_node != parent and not self.removed[next_node]:\n self.subtree_size[node] += self._compute_size(next_node, node)\n return self.subtree_size[node]\n\n def _find_centroid(self, node, parent, tree_size):\n \"\"\"Find centroid by descending into any child subtree > tree_size/2.\"\"\"\n for next_node, _ in self.adj[node]:\n if next_node != parent and not self.removed[next_node]:\n if self.subtree_size[next_node] > tree_size // 2:\n return self._find_centroid(next_node, node, tree_size)\n return node\n\n def _compute_distances(self, node, parent, dist, centroid_depth):\n \"\"\"Store distance from current centroid to all nodes in its subtree.\"\"\"\n self.dist_to_ancestor[node][centroid_depth] = dist\n for next_node, weight in self.adj[node]:\n if next_node != parent and not self.removed[next_node]:\n self._compute_distances(next_node, node, dist + weight, centroid_depth)\n\n def build(self, node, parent, d):\n \"\"\"Build centroid decomposition starting from node.\"\"\"\n tree_size = self._compute_size(node, -1)\n centroid = self._find_centroid(node, -1, tree_size)\n\n self.removed[centroid] = True\n self.centroid_parent[centroid] = parent\n self.depth[centroid] = d\n\n # Distance from centroid to itself is 0\n self.dist_to_ancestor[centroid][d] = 0\n\n # Compute distances from centroid to all reachable nodes\n for next_node, weight in self.adj[centroid]:\n if not self.removed[next_node]:\n self._compute_distances(next_node, centroid, weight, d)\n\n # Recurse on remaining subtrees\n for next_node, _ in self.adj[centroid]:\n if not self.removed[next_node]:\n self.build(next_node, centroid, d + 1)\n\n def query(self, u, v):\n \"\"\"Find distance between u and v using centroid tree ancestors.\"\"\"\n min_dist = float('inf')\n max_level = min(self.depth[u], self.depth[v])\n for d in range(max_level + 1):\n candidate = self.dist_to_ancestor[u][d] + self.dist_to_ancestor[v][d]\n if candidate < min_dist:\n min_dist = candidate\n return min_dist\n\n# Example usage\nif __name__ == \"__main__\":\n n = 7\n cd = CentroidDecomposition(n)\n cd.add_edge(1, 2, 1)\n cd.add_edge(1, 3, 1)\n cd.add_edge(2, 4, 1)\n cd.add_edge(2, 5, 1)\n cd.add_edge(3, 6, 1)\n cd.add_edge(5, 7, 1)\n\n cd.build(1, 0, 0)\n\n print(f\"dist(4,6) = {cd.query(4, 6)}\") # 4\n print(f\"dist(7,3) = {cd.query(7, 3)}\") # 4\n print(f\"dist(4,7) = {cd.query(4, 7)}\") # 3\n```\n\n```cpp\n#include \n#include \n#include \n#include \nusing namespace std;\n\nclass CentroidDecomposition {\n int n;\n vector>> adj; // adj[u] = {(v, weight), ...}\n vector subtreeSize;\n vector removed;\n vector centroidParent;\n vector depth;\n vector> distToAncestor;\n\n int computeSize(int node, int parent) {\n subtreeSize[node] = 1;\n for (auto& [next, w] : adj[node]) {\n if (next != parent && !removed[next]) {\n subtreeSize[node] += computeSize(next, node);\n }\n }\n return subtreeSize[node];\n }\n\n int findCentroid(int node, int parent, int treeSize) {\n for (auto& [next, w] : adj[node]) {\n if (next != parent && !removed[next]) {\n if (subtreeSize[next] > treeSize / 2) {\n return findCentroid(next, node, treeSize);\n }\n }\n }\n return node;\n }\n\n void computeDistances(int node, int parent, long long dist, int centroidDepth) {\n distToAncestor[node][centroidDepth] = dist;\n for (auto& [next, weight] : adj[node]) {\n if (next != parent && !removed[next]) {\n computeDistances(next, node, dist + weight, centroidDepth);\n }\n }\n }\n\npublic:\n CentroidDecomposition(int n) : n(n) {\n adj.resize(n + 1);\n subtreeSize.resize(n + 1, 0);\n removed.resize(n + 1, false);\n centroidParent.resize(n + 1, 0);\n depth.resize(n + 1, 0);\n int maxDepth = (int)(log2(n)) + 2;\n distToAncestor.assign(n + 1, vector(maxDepth + 1, 0));\n }\n\n void addEdge(int u, int v, int w) {\n adj[u].push_back({v, w});\n adj[v].push_back({u, w});\n }\n\n void build(int node, int parent, int d) {\n int treeSize = computeSize(node, -1);\n int centroid = findCentroid(node, -1, treeSize);\n\n removed[centroid] = true;\n centroidParent[centroid] = parent;\n depth[centroid] = d;\n\n distToAncestor[centroid][d] = 0;\n for (auto& [next, weight] : adj[centroid]) {\n if (!removed[next]) {\n computeDistances(next, centroid, (long long)weight, d);\n }\n }\n\n for (auto& [next, w] : adj[centroid]) {\n if (!removed[next]) {\n build(next, centroid, d + 1);\n }\n }\n }\n\n long long query(int u, int v) {\n long long minDist = LLONG_MAX;\n int maxLevel = min(depth[u], depth[v]);\n for (int d = 0; d <= maxLevel; d++) {\n long long candidate = distToAncestor[u][d] + distToAncestor[v][d];\n if (candidate < minDist) {\n minDist = candidate;\n }\n }\n return minDist;\n }\n};\n\nint main() {\n int n = 7;\n CentroidDecomposition cd(n);\n cd.addEdge(1, 2, 1);\n cd.addEdge(1, 3, 1);\n cd.addEdge(2, 4, 1);\n cd.addEdge(2, 5, 1);\n cd.addEdge(3, 6, 1);\n cd.addEdge(5, 7, 1);\n\n cd.build(1, 0, 0);\n\n // dist(4,6) = 4, dist(7,3) = 4, dist(4,7) = 3\n cout << \"dist(4,6) = \" << cd.query(4, 6) << endl;\n cout << \"dist(7,3) = \" << cd.query(7, 3) << endl;\n cout << \"dist(4,7) = \" << cd.query(4, 7) << endl;\n\n return 0;\n}\n```\n\n```csharp\nusing System;\nusing System.Collections.Generic;\n\nclass CentroidDecomposition\n{\n private List<(int next, int weight)>[] adj; // adj[u] = list of (v, weight)\n private int[] subtreeSize;\n private bool[] removed;\n private int[] centroidParent;\n private long[][] distToAncestor; // distToAncestor[node][level]\n private int[] depth; // depth of each node in centroid tree\n private int n;\n\n public CentroidDecomposition(int n)\n {\n this.n = n;\n adj = new List<(int, int)>[n + 1];\n for (int i = 0; i <= n; i++)\n {\n adj[i] = new List<(int, int)>();\n }\n subtreeSize = new int[n + 1];\n removed = new bool[n + 1];\n centroidParent = new int[n + 1];\n depth = new int[n + 1];\n // O(log n) ancestors at most\n int maxDepth = (int)(Math.Log(n) / Math.Log(2)) + 2;\n distToAncestor = new long[n + 1][];\n for (int i = 0; i <= n; i++)\n {\n distToAncestor[i] = new long[maxDepth + 1];\n }\n }\n\n public void AddEdge(int u, int v, int w)\n {\n adj[u].Add((v, w));\n adj[v].Add((u, w));\n }\n\n // Compute subtree sizes rooted at 'node', skipping removed nodes\n private int ComputeSize(int node, int parent)\n {\n subtreeSize[node] = 1;\n foreach (var (next, w) in adj[node])\n {\n if (next != parent && !removed[next])\n {\n subtreeSize[node] += ComputeSize(next, node);\n }\n }\n return subtreeSize[node];\n }\n\n // Find centroid of the subtree rooted at 'node'\n private int FindCentroid(int node, int parent, int treeSize)\n {\n foreach (var (next, w) in adj[node])\n {\n if (next != parent && !removed[next])\n {\n // If this child's subtree has more than half the nodes,\n // the centroid must be in that subtree\n if (subtreeSize[next] > treeSize / 2)\n {\n return FindCentroid(next, node, treeSize);\n }\n }\n }\n // No child subtree exceeds treeSize/2, so the current node is the centroid.\n return node;\n }\n\n // Store distances from 'centroid' (at given depth) to all nodes in its subtree\n private void ComputeDistances(int node, int parent, long dist, int centroidDepth)\n {\n distToAncestor[node][centroidDepth] = dist;\n foreach (var (next, weight) in adj[node])\n {\n if (next != parent && !removed[next])\n {\n ComputeDistances(next, node, dist + weight, centroidDepth);\n }\n }\n }\n\n // Build centroid decomposition starting from 'node'\n public void Build(int node, int parent, int d)\n {\n int treeSize = ComputeSize(node, -1);\n int centroid = FindCentroid(node, -1, treeSize);\n\n removed[centroid] = true;\n centroidParent[centroid] = parent;\n depth[centroid] = d;\n\n // Store distance from centroid to itself\n distToAncestor[centroid][d] = 0;\n // Compute distances from centroid to all nodes in current subtree\n foreach (var (next, weight) in adj[centroid])\n {\n if (!removed[next])\n {\n ComputeDistances(next, centroid, weight, d);\n }\n }\n\n // Recurse on each remaining subtree\n foreach (var (next, w) in adj[centroid])\n {\n if (!removed[next])\n {\n Build(next, centroid, d + 1);\n }\n }\n }\n\n // Query distance between u and v using centroid tree\n public long Query(int u, int v)\n {\n long minDist = long.MaxValue;\n // For every common ancestor c of u and v in the centroid tree,\n // dist(u, v) through c = dist(u, c) + dist(v, c). The minimum is\n // the true distance.\n int maxLevel = Math.Min(depth[u], depth[v]);\n for (int d = 0; d <= maxLevel; d++)\n {\n long candidate = distToAncestor[u][d] + distToAncestor[v][d];\n if (candidate < minDist)\n {\n minDist = candidate;\n }\n }\n return minDist;\n }\n\n public static void Main(string[] args)\n {\n // Example tree:\n // 1\n // / \\\n // 2 3\n // / \\ \\\n // 4 5 6\n // |\n // 7\n int n = 7;\n CentroidDecomposition cd = new CentroidDecomposition(n);\n cd.AddEdge(1, 2, 1);\n cd.AddEdge(1, 3, 1);\n cd.AddEdge(2, 4, 1);\n cd.AddEdge(2, 5, 1);\n cd.AddEdge(3, 6, 1);\n cd.AddEdge(5, 7, 1);\n\n cd.Build(1, 0, 0);\n\n // Distance from 4 to 6: path is 4-2-1-3-6, distance = 4\n Console.WriteLine(\"dist(4,6) = \" + cd.Query(4, 6));\n // Distance from 7 to 3: path is 7-5-2-1-3, distance = 4\n Console.WriteLine(\"dist(7,3) = \" + cd.Query(7, 3));\n // Distance from 4 to 7: path is 4-2-5-7, distance = 3\n Console.WriteLine(\"dist(4,7) = \" + cd.Query(4, 7));\n }\n}\n```\n\n```go\npackage main\n\nimport (\n\t\"fmt\"\n\t\"math\"\n\t\"math/bits\"\n)\n\ntype edge struct {\n\tnext int\n\tweight int\n}\n\ntype CentroidDecomposition struct {\n\tn int\n\tadj [][]edge // adj[u] = list of {next, weight}\n\tsubtreeSize []int\n\tremoved []bool\n\tcentroidParent []int\n\tdistToAncestor [][]int64 // distToAncestor[node][level]\n\tdepth []int // depth of each node in centroid tree\n}\n\nfunc NewCentroidDecomposition(n int) *CentroidDecomposition {\n\tcd := &CentroidDecomposition{n: n}\n\tcd.adj = make([][]edge, n+1)\n\tcd.subtreeSize = make([]int, n+1)\n\tcd.removed = make([]bool, n+1)\n\tcd.centroidParent = make([]int, n+1)\n\tcd.depth = make([]int, n+1)\n\t// O(log n) ancestors at most\n\tmaxDepth := 2\n\tif n > 1 {\n\t\tmaxDepth = bits.Len(uint(n)) + 1\n\t}\n\tcd.distToAncestor = make([][]int64, n+1)\n\tfor i := 0; i <= n; i++ {\n\t\tcd.distToAncestor[i] = make([]int64, maxDepth+1)\n\t}\n\treturn cd\n}\n\nfunc (cd *CentroidDecomposition) AddEdge(u, v, w int) {\n\tcd.adj[u] = append(cd.adj[u], edge{v, w})\n\tcd.adj[v] = append(cd.adj[v], edge{u, w})\n}\n\n// computeSize computes subtree sizes rooted at 'node', skipping removed nodes\nfunc (cd *CentroidDecomposition) computeSize(node, parent int) int {\n\tcd.subtreeSize[node] = 1\n\tfor _, e := range cd.adj[node] {\n\t\tif e.next != parent && !cd.removed[e.next] {\n\t\t\tcd.subtreeSize[node] += cd.computeSize(e.next, node)\n\t\t}\n\t}\n\treturn cd.subtreeSize[node]\n}\n\n// findCentroid finds the centroid of the subtree rooted at 'node'\nfunc (cd *CentroidDecomposition) findCentroid(node, parent, treeSize int) int {\n\tfor _, e := range cd.adj[node] {\n\t\tif e.next != parent && !cd.removed[e.next] {\n\t\t\t// If this child's subtree has more than half the nodes,\n\t\t\t// the centroid must be in that subtree\n\t\t\tif cd.subtreeSize[e.next] > treeSize/2 {\n\t\t\t\treturn cd.findCentroid(e.next, node, treeSize)\n\t\t\t}\n\t\t}\n\t}\n\t// No child subtree exceeds treeSize/2, so the current node is the centroid.\n\treturn node\n}\n\n// computeDistances stores distances from 'centroid' to all nodes in its subtree\nfunc (cd *CentroidDecomposition) computeDistances(node, parent int, dist int64, centroidDepth int) {\n\tcd.distToAncestor[node][centroidDepth] = dist\n\tfor _, e := range cd.adj[node] {\n\t\tif e.next != parent && !cd.removed[e.next] {\n\t\t\tcd.computeDistances(e.next, node, dist+int64(e.weight), centroidDepth)\n\t\t}\n\t}\n}\n\n// Build builds the centroid decomposition starting from 'node'\nfunc (cd *CentroidDecomposition) Build(node, parent, d int) {\n\ttreeSize := cd.computeSize(node, -1)\n\tcentroid := cd.findCentroid(node, -1, treeSize)\n\n\tcd.removed[centroid] = true\n\tcd.centroidParent[centroid] = parent\n\tcd.depth[centroid] = d\n\n\t// Store distance from centroid to itself\n\tcd.distToAncestor[centroid][d] = 0\n\t// Compute distances from centroid to all nodes in current subtree\n\tfor _, e := range cd.adj[centroid] {\n\t\tif !cd.removed[e.next] {\n\t\t\tcd.computeDistances(e.next, centroid, int64(e.weight), d)\n\t\t}\n\t}\n\n\t// Recurse on each remaining subtree\n\tfor _, e := range cd.adj[centroid] {\n\t\tif !cd.removed[e.next] {\n\t\t\tcd.Build(e.next, centroid, d+1)\n\t\t}\n\t}\n}\n\n// Query returns the distance between u and v using the centroid tree\nfunc (cd *CentroidDecomposition) Query(u, v int) int64 {\n\tminDist := int64(math.MaxInt64)\n\t// For every common ancestor c of u and v in the centroid tree,\n\t// dist(u, v) through c = dist(u, c) + dist(v, c). The minimum is\n\t// the true distance.\n\tmaxLevel := cd.depth[u]\n\tif cd.depth[v] < maxLevel {\n\t\tmaxLevel = cd.depth[v]\n\t}\n\tfor d := 0; d <= maxLevel; d++ {\n\t\tcandidate := cd.distToAncestor[u][d] + cd.distToAncestor[v][d]\n\t\tif candidate < minDist {\n\t\t\tminDist = candidate\n\t\t}\n\t}\n\treturn minDist\n}\n\nfunc main() {\n\t// Example tree:\n\t// 1\n\t// / \\\n\t// 2 3\n\t// / \\ \\\n\t// 4 5 6\n\t// |\n\t// 7\n\tn := 7\n\tcd := NewCentroidDecomposition(n)\n\tcd.AddEdge(1, 2, 1)\n\tcd.AddEdge(1, 3, 1)\n\tcd.AddEdge(2, 4, 1)\n\tcd.AddEdge(2, 5, 1)\n\tcd.AddEdge(3, 6, 1)\n\tcd.AddEdge(5, 7, 1)\n\n\tcd.Build(1, 0, 0)\n\n\t// Distance from 4 to 6: path is 4-2-1-3-6, distance = 4\n\tfmt.Println(\"dist(4,6) =\", cd.Query(4, 6))\n\t// Distance from 7 to 3: path is 7-5-2-1-3, distance = 4\n\tfmt.Println(\"dist(7,3) =\", cd.Query(7, 3))\n\t// Distance from 4 to 7: path is 4-2-5-7, distance = 3\n\tfmt.Println(\"dist(4,7) =\", cd.Query(4, 7))\n}\n```\n\n```rust\nstruct CentroidDecomposition {\n n: usize,\n adj: Vec>, // adj[u] = list of (next, weight)\n subtree_size: Vec,\n removed: Vec,\n centroid_parent: Vec,\n dist_to_ancestor: Vec>, // dist_to_ancestor[node][level]\n depth: Vec, // depth of each node in centroid tree\n}\n\nimpl CentroidDecomposition {\n fn new(n: usize) -> Self {\n // O(log n) ancestors at most\n let max_depth = if n > 1 {\n (n as f64).log2() as usize + 2\n } else {\n 2\n };\n CentroidDecomposition {\n n,\n adj: vec![Vec::new(); n + 1],\n subtree_size: vec![0; n + 1],\n removed: vec![false; n + 1],\n centroid_parent: vec![0; n + 1],\n dist_to_ancestor: vec![vec![0; max_depth + 1]; n + 1],\n depth: vec![0; n + 1],\n }\n }\n\n fn add_edge(&mut self, u: usize, v: usize, w: i64) {\n self.adj[u].push((v, w));\n self.adj[v].push((u, w));\n }\n\n // Compute subtree sizes rooted at 'node', skipping removed nodes\n fn compute_size(&mut self, node: usize, parent: i64) -> usize {\n self.subtree_size[node] = 1;\n // Iterate over indices to avoid borrowing self.adj while mutating self\n let len = self.adj[node].len();\n for i in 0..len {\n let (next, _) = self.adj[node][i];\n if next as i64 != parent && !self.removed[next] {\n self.subtree_size[node] += self.compute_size(next, node as i64);\n }\n }\n self.subtree_size[node]\n }\n\n // Find centroid of the subtree rooted at 'node'\n fn find_centroid(&self, node: usize, parent: i64, tree_size: usize) -> usize {\n for &(next, _) in &self.adj[node] {\n if next as i64 != parent && !self.removed[next] {\n // If this child's subtree has more than half the nodes,\n // the centroid must be in that subtree\n if self.subtree_size[next] > tree_size / 2 {\n return self.find_centroid(next, node as i64, tree_size);\n }\n }\n }\n // No child subtree exceeds tree_size/2, so the current node is the centroid.\n node\n }\n\n // Store distances from 'centroid' (at given depth) to all nodes in its subtree\n fn compute_distances(&mut self, node: usize, parent: i64, dist: i64, centroid_depth: usize) {\n self.dist_to_ancestor[node][centroid_depth] = dist;\n let len = self.adj[node].len();\n for i in 0..len {\n let (next, weight) = self.adj[node][i];\n if next as i64 != parent && !self.removed[next] {\n self.compute_distances(next, node as i64, dist + weight, centroid_depth);\n }\n }\n }\n\n // Build centroid decomposition starting from 'node'\n fn build(&mut self, node: usize, parent: i64, d: usize) {\n let tree_size = self.compute_size(node, -1);\n let centroid = self.find_centroid(node, -1, tree_size);\n\n self.removed[centroid] = true;\n self.centroid_parent[centroid] = parent;\n self.depth[centroid] = d;\n\n // Store distance from centroid to itself\n self.dist_to_ancestor[centroid][d] = 0;\n // Compute distances from centroid to all nodes in current subtree\n let len = self.adj[centroid].len();\n for i in 0..len {\n let (next, weight) = self.adj[centroid][i];\n if !self.removed[next] {\n self.compute_distances(next, centroid as i64, weight, d);\n }\n }\n\n // Recurse on each remaining subtree\n for i in 0..len {\n let (next, _) = self.adj[centroid][i];\n if !self.removed[next] {\n self.build(next, centroid as i64, d + 1);\n }\n }\n }\n\n // Query distance between u and v using centroid tree\n fn query(&self, u: usize, v: usize) -> i64 {\n let mut min_dist = i64::MAX;\n // For every common ancestor c of u and v in the centroid tree,\n // dist(u, v) through c = dist(u, c) + dist(v, c). The minimum is\n // the true distance.\n let max_level = self.depth[u].min(self.depth[v]);\n for d in 0..=max_level {\n let candidate = self.dist_to_ancestor[u][d] + self.dist_to_ancestor[v][d];\n if candidate < min_dist {\n min_dist = candidate;\n }\n }\n min_dist\n }\n}\n\nfn main() {\n // Example tree:\n // 1\n // / \\\n // 2 3\n // / \\ \\\n // 4 5 6\n // |\n // 7\n let n = 7;\n let mut cd = CentroidDecomposition::new(n);\n cd.add_edge(1, 2, 1);\n cd.add_edge(1, 3, 1);\n cd.add_edge(2, 4, 1);\n cd.add_edge(2, 5, 1);\n cd.add_edge(3, 6, 1);\n cd.add_edge(5, 7, 1);\n\n cd.build(1, 0, 0);\n\n // Distance from 4 to 6: path is 4-2-1-3-6, distance = 4\n println!(\"dist(4,6) = {}\", cd.query(4, 6));\n // Distance from 7 to 3: path is 7-5-2-1-3, distance = 4\n println!(\"dist(7,3) = {}\", cd.query(7, 3));\n // Distance from 4 to 7: path is 4-2-5-7, distance = 3\n println!(\"dist(4,7) = {}\", cd.query(4, 7));\n}\n```\n\n```javascript\nclass CentroidDecomposition {\n constructor(n) {\n this.n = n;\n this.adj = Array.from({ length: n + 1 }, () => []); // adj[u] = [[v, weight], ...]\n this.subtreeSize = new Array(n + 1).fill(0);\n this.removed = new Array(n + 1).fill(false);\n this.centroidParent = new Array(n + 1).fill(0);\n this.depth = new Array(n + 1).fill(0);\n // O(log n) ancestors at most\n const maxDepth = n > 0 ? Math.floor(Math.log2(n)) + 2 : 1;\n this.distToAncestor = Array.from({ length: n + 1 }, () =>\n new Array(maxDepth + 1).fill(0)\n );\n }\n\n addEdge(u, v, w) {\n this.adj[u].push([v, w]);\n this.adj[v].push([u, w]);\n }\n\n // Compute subtree sizes rooted at 'node', skipping removed nodes\n computeSize(node, parent) {\n this.subtreeSize[node] = 1;\n for (const [next] of this.adj[node]) {\n if (next !== parent && !this.removed[next]) {\n this.subtreeSize[node] += this.computeSize(next, node);\n }\n }\n return this.subtreeSize[node];\n }\n\n // Find centroid of the subtree rooted at 'node'\n findCentroid(node, parent, treeSize) {\n for (const [next] of this.adj[node]) {\n if (next !== parent && !this.removed[next]) {\n // If this child's subtree has more than half the nodes,\n // the centroid must be in that subtree\n if (this.subtreeSize[next] > Math.floor(treeSize / 2)) {\n return this.findCentroid(next, node, treeSize);\n }\n }\n }\n // No child subtree exceeds treeSize/2, so the current node is the centroid.\n return node;\n }\n\n // Store distances from 'centroid' (at given depth) to all nodes in its subtree\n computeDistances(node, parent, dist, centroidDepth) {\n this.distToAncestor[node][centroidDepth] = dist;\n for (const [next, weight] of this.adj[node]) {\n if (next !== parent && !this.removed[next]) {\n this.computeDistances(next, node, dist + weight, centroidDepth);\n }\n }\n }\n\n // Build centroid decomposition starting from 'node'\n build(node, parent, d) {\n const treeSize = this.computeSize(node, -1);\n const centroid = this.findCentroid(node, -1, treeSize);\n\n this.removed[centroid] = true;\n this.centroidParent[centroid] = parent;\n this.depth[centroid] = d;\n\n // Store distance from centroid to itself\n this.distToAncestor[centroid][d] = 0;\n // Compute distances from centroid to all nodes in current subtree\n for (const [next, weight] of this.adj[centroid]) {\n if (!this.removed[next]) {\n this.computeDistances(next, centroid, weight, d);\n }\n }\n\n // Recurse on each remaining subtree\n for (const [next] of this.adj[centroid]) {\n if (!this.removed[next]) {\n this.build(next, centroid, d + 1);\n }\n }\n }\n\n // Query distance between u and v using centroid tree\n query(u, v) {\n let minDist = Infinity;\n // For every common ancestor c of u and v in the centroid tree,\n // dist(u, v) through c = dist(u, c) + dist(v, c). The minimum is\n // the true distance.\n const maxLevel = Math.min(this.depth[u], this.depth[v]);\n for (let d = 0; d <= maxLevel; d++) {\n const candidate = this.distToAncestor[u][d] + this.distToAncestor[v][d];\n if (candidate < minDist) {\n minDist = candidate;\n }\n }\n return minDist;\n }\n}\n\n// Example tree:\n// 1\n// / \\\n// 2 3\n// / \\ \\\n// 4 5 6\n// |\n// 7\nconst n = 7;\nconst cd = new CentroidDecomposition(n);\ncd.addEdge(1, 2, 1);\ncd.addEdge(1, 3, 1);\ncd.addEdge(2, 4, 1);\ncd.addEdge(2, 5, 1);\ncd.addEdge(3, 6, 1);\ncd.addEdge(5, 7, 1);\n\ncd.build(1, 0, 0);\n\n// Distance from 4 to 6: path is 4-2-1-3-6, distance = 4\nconsole.log(\"dist(4,6) = \" + cd.query(4, 6));\n// Distance from 7 to 3: path is 7-5-2-1-3, distance = 4\nconsole.log(\"dist(7,3) = \" + cd.query(7, 3));\n// Distance from 4 to 7: path is 4-2-5-7, distance = 3\nconsole.log(\"dist(4,7) = \" + cd.query(4, 7));\n```\n\n```typescript\nclass CentroidDecomposition {\n private n: number;\n private adj: Array>; // adj[u] = [[v, weight], ...]\n private subtreeSize: number[];\n private removed: boolean[];\n private centroidParent: number[];\n private depth: number[]; // depth of each node in centroid tree\n private distToAncestor: number[][]; // distToAncestor[node][level]\n\n constructor(n: number) {\n this.n = n;\n this.adj = Array.from({ length: n + 1 }, () => [] as Array<[number, number]>);\n this.subtreeSize = new Array(n + 1).fill(0);\n this.removed = new Array(n + 1).fill(false);\n this.centroidParent = new Array(n + 1).fill(0);\n this.depth = new Array(n + 1).fill(0);\n // O(log n) ancestors at most\n const maxDepth = n > 0 ? Math.floor(Math.log2(n)) + 2 : 1;\n this.distToAncestor = Array.from({ length: n + 1 }, () =>\n new Array(maxDepth + 1).fill(0)\n );\n }\n\n addEdge(u: number, v: number, w: number): void {\n this.adj[u].push([v, w]);\n this.adj[v].push([u, w]);\n }\n\n // Compute subtree sizes rooted at 'node', skipping removed nodes\n private computeSize(node: number, parent: number): number {\n this.subtreeSize[node] = 1;\n for (const [next] of this.adj[node]) {\n if (next !== parent && !this.removed[next]) {\n this.subtreeSize[node] += this.computeSize(next, node);\n }\n }\n return this.subtreeSize[node];\n }\n\n // Find centroid of the subtree rooted at 'node'\n private findCentroid(node: number, parent: number, treeSize: number): number {\n for (const [next] of this.adj[node]) {\n if (next !== parent && !this.removed[next]) {\n // If this child's subtree has more than half the nodes,\n // the centroid must be in that subtree\n if (this.subtreeSize[next] > Math.floor(treeSize / 2)) {\n return this.findCentroid(next, node, treeSize);\n }\n }\n }\n // No child subtree exceeds treeSize/2, so the current node is the centroid.\n return node;\n }\n\n // Store distances from 'centroid' (at given depth) to all nodes in its subtree\n private computeDistances(node: number, parent: number, dist: number, centroidDepth: number): void {\n this.distToAncestor[node][centroidDepth] = dist;\n for (const [next, weight] of this.adj[node]) {\n if (next !== parent && !this.removed[next]) {\n this.computeDistances(next, node, dist + weight, centroidDepth);\n }\n }\n }\n\n // Build centroid decomposition starting from 'node'\n build(node: number, parent: number, d: number): void {\n const treeSize = this.computeSize(node, -1);\n const centroid = this.findCentroid(node, -1, treeSize);\n\n this.removed[centroid] = true;\n this.centroidParent[centroid] = parent;\n this.depth[centroid] = d;\n\n // Store distance from centroid to itself\n this.distToAncestor[centroid][d] = 0;\n // Compute distances from centroid to all nodes in current subtree\n for (const [next, weight] of this.adj[centroid]) {\n if (!this.removed[next]) {\n this.computeDistances(next, centroid, weight, d);\n }\n }\n\n // Recurse on each remaining subtree\n for (const [next] of this.adj[centroid]) {\n if (!this.removed[next]) {\n this.build(next, centroid, d + 1);\n }\n }\n }\n\n // Query distance between u and v using centroid tree\n query(u: number, v: number): number {\n let minDist = Infinity;\n // For every common ancestor c of u and v in the centroid tree,\n // dist(u, v) through c = dist(u, c) + dist(v, c). The minimum is\n // the true distance.\n const maxLevel = Math.min(this.depth[u], this.depth[v]);\n for (let d = 0; d <= maxLevel; d++) {\n const candidate = this.distToAncestor[u][d] + this.distToAncestor[v][d];\n if (candidate < minDist) {\n minDist = candidate;\n }\n }\n return minDist;\n }\n}\n\n// Example tree:\n// 1\n// / \\\n// 2 3\n// / \\ \\\n// 4 5 6\n// |\n// 7\nconst n: number = 7;\nconst cd = new CentroidDecomposition(n);\ncd.addEdge(1, 2, 1);\ncd.addEdge(1, 3, 1);\ncd.addEdge(2, 4, 1);\ncd.addEdge(2, 5, 1);\ncd.addEdge(3, 6, 1);\ncd.addEdge(5, 7, 1);\n\ncd.build(1, 0, 0);\n\n// Distance from 4 to 6: path is 4-2-1-3-6, distance = 4\nconsole.log(\"dist(4,6) = \" + cd.query(4, 6));\n// Distance from 7 to 3: path is 7-5-2-1-3, distance = 4\nconsole.log(\"dist(7,3) = \" + cd.query(7, 3));\n// Distance from 4 to 7: path is 4-2-5-7, distance = 3\nconsole.log(\"dist(4,7) = \" + cd.query(4, 7));\n```\n\n\n---\n\n# Code Explanation\n\nLet us walk through the key parts of the implementation.\n\n### computeSize (DFS for Subtree Sizes)\n\nThis function roots the current (non-removed) subtree at an arbitrary node and computes how many nodes each subtree contains. It skips any node already marked as `removed`, because those nodes were centroids at a previous level and are no longer part of the current subproblem. This is a standard DFS that runs in O(size of current component).\n\n### findCentroid (Greedy Descent)\n\nRather than checking every node, this function uses a greedy approach. Starting at any node, it looks at each child's subtree size. If a child's subtree has more than treeSize/2 nodes, the centroid must be in that subtree (because removing the current node would leave a component too large). So it descends into that child and repeats. When no child has a subtree exceeding treeSize/2, the current node is the centroid.\n\nThis works because the \"upward\" component for any node in the descent path keeps getting smaller as we go deeper, while the large child subtree keeps shrinking as we enter it. The process converges to the centroid in O(n) time.\n\n### computeDistances (Precomputing Ancestor Distances)\n\nFor the distance query application, we need to know the distance from every node to each of its ancestors in the centroid tree. When we find centroid c at depth d, we run a DFS from c to all non-removed nodes and store `distToAncestor[node][d] = distance from node to c`. This way, when we later query distance(u, v), we can check every common ancestor depth and compute `distToAncestor[u][d] + distToAncestor[v][d]`.\n\n### query (Distance Lookup)\n\nThe distance between u and v in the original tree equals `distToAncestor[u][d] + distToAncestor[v][d]` where d is the depth of their LCA in the centroid tree. Since we do not explicitly compute the LCA, we check all depths from 0 to min(depth[u], depth[v]) and take the minimum. The correct LCA depth will give the true distance, and all other depths give upper bounds (because the triangle inequality holds), so the minimum is the correct answer.\n\n### Common Mistakes\n\n- **Forgetting to recompute subtree sizes.** You must call `computeSize` at the start of each recursive call, not reuse sizes from a previous round. After removing centroids, the component structure changes, and old subtree sizes are invalid.\n- **Not skipping removed nodes.** Every DFS (size computation, centroid finding, distance computation) must check the `removed` flag. Forgetting this causes nodes to be visited across component boundaries, leading to incorrect centroids and wrong answers.\n- **Off-by-one in max depth.** The centroid tree has depth O(log n), but you need to allocate slightly more than log2(n) levels in your distance array to avoid index-out-of-bounds errors. Adding 2 to `log2(n)` is a safe margin.\n- **Integer overflow in distance sums.** When edge weights are large and the tree is deep, the sum of distances can overflow 32-bit integers. Use `long` (Java), `int` (Python handles big integers natively), or `long long` (C++).\n\n---\n\n# Complexity Analysis\n\n### Build Time: O(n log n)\n\nThe build time is O(n log n), and here is why.\n\nThe recursion has O(log n) levels. At each level, the centroid splits the current tree into subtrees of size at most n/2, so the depth doubles at most log2(n) times before reaching size 1.\n\nAt each level of the recursion, the total work across all subproblems is O(n). This is because the subtrees at any given recursion level form a partition of the n nodes (each node belongs to exactly one subtree at each level). Computing sizes, finding the centroid, and computing distances for a subtree of size s all take O(s) time, and the sizes sum to n.\n\nTherefore: O(log n) levels times O(n) work per level = **O(n log n)** total.\n\nThis is the same reasoning that gives merge sort its O(n log n) complexity. Each level processes all n elements, and there are O(log n) levels.\n\n### Query Time: O(log n)\n\nEach query checks all depths from 0 to the depth of the shallower node. Since the centroid tree has depth O(log n), each query takes O(log n) time.\n\n### Space: O(n log n)\n\nThe dominant space cost is the `distToAncestor` table: n nodes, each storing distances to O(log n) ancestors. The adjacency list, size arrays, and boolean flags all use O(n) space.\n\n\n| Operation | Time | Space |\n|-----------|------|-------|\n| Build centroid tree | O(n log n) | O(n log n) |\n| Distance query | O(log n) | O(1) per query |\n| Mark/unmark node | O(log n) | O(1) per update |\n\n\n---\n\n# Variations and Extensions\n\n### Variation 1: Closest Marked Node (Dynamic Updates)\n\nThis is one of the most practical applications. You maintain a set of \"marked\" nodes that changes over time, and you need to answer queries of the form \"what is the closest marked node to u?\"\n\nFor each node in the centroid tree, maintain a value `best[c]` representing the minimum distance from c to any marked node in c's subtree (in the centroid tree). When you mark node u, walk up from u to the root of the centroid tree, updating `best[ancestor] = min(best[ancestor], dist(u, ancestor))`. When you query node u, walk up the same path and compute `min over all ancestors a of (best[a] + dist(u, a))`.\n\nBoth update and query walk O(log n) ancestors, so they take O(log n) time each.\n\n### Variation 2: Counting Paths of Weight K\n\nGiven a tree with weighted edges, count the number of paths with total weight exactly k. At each centroid c, compute the distance from c to every node in its subtree. Store these distances in a frequency map. For each distance d, the number of paths through c with weight k is the number of nodes at distance d times the number of nodes at distance k - d (being careful not to double count paths within the same child subtree).\n\nThis gives an O(n log n) algorithm for the entire counting problem. The classic version of this problem is known as \"Race\" or \"IOI 2011 Race.\"\n\n### Variation 3: Centroid Decomposition with Edge Updates\n\nIf edge weights change, you cannot use the precomputed distance table directly. However, the structure of the centroid tree does not change (it depends only on the tree's topology, not the weights). You can rebuild the distance tables in O(n log n) after weight changes, or use lazy techniques to handle updates more efficiently for specific problem types.\n\n### Comparison Table\n\n\n| Variant | Build Time | Update Time | Query Time | Best For |\n|---------|-----------|-------------|------------|----------|\n| Static distance queries | O(n log n) | N/A | O(log n) | Fixed tree, many distance queries |\n| Closest marked node | O(n log n) | O(log n) | O(log n) | Dynamic marking, nearest neighbor |\n| Count paths of weight k | O(n log n) | N/A | Single pass | One-time counting |\n\n\n---\n\n# Comparison with Related Structures\n\nCentroid decomposition is not the only way to handle tree path queries. Here is how it compares to the alternatives.\n\n\n| Technique | Build Time | Query Time | Handles Updates | Best For |\n|-----------|-----------|------------|-----------------|----------|\n| **Centroid Decomposition** | O(n log n) | O(log n) | Yes (O(log n)) | Distance queries, path counting, closest marked node |\n| **Heavy-Light Decomposition (HLD)** | O(n) | O(log^2 n) | Yes (O(log^2 n)) | Path aggregates (sum, max, min) with segment tree |\n| **Euler Tour + Segment Tree** | O(n) | O(log n) for subtree | Subtree only | Subtree queries (sum, min, max) |\n| **LCA + Sparse Table** | O(n log n) | O(1) for LCA | No | LCA queries, distance in unweighted trees |\n\n\n### When to Choose Centroid Decomposition\n\n- **Distance queries between arbitrary pairs.** Centroid decomposition gives O(log n) per query with simple implementation. HLD with a segment tree can also do this, but the code is more involved.\n- **Counting or enumerating paths with a property.** The divide-and-conquer nature of centroid decomposition is perfect for this: at each centroid, you process all paths passing through it. HLD does not naturally support this.\n- **Dynamic nearest neighbor on trees.** The \"closest marked node\" problem is a natural fit. HLD can solve it too, but the centroid decomposition approach is cleaner.\n\n### When NOT to Use Centroid Decomposition\n\n- **Subtree queries only.** If your queries only involve subtrees (not arbitrary paths), Euler tour + segment tree is simpler and faster.\n- **Path aggregate queries with updates.** If you need to update edge weights and query path sums or path maximums, HLD with a segment tree is the standard tool. Centroid decomposition can handle this, but it is not the natural fit.\n- **Simple LCA queries.** If all you need is the lowest common ancestor, use sparse tables or binary lifting. Centroid decomposition is overkill.\n\n---\n\n# Common Patterns and Applications\n\n### Pattern 1: Distance Queries\n\n**Problem type:** Given a tree with weighted edges and q queries, each asking for the distance between two nodes u and v.\n\n**How centroid decomposition helps:** Build the centroid tree and precompute distances from each node to all its centroid tree ancestors. Each query is answered in O(log n) by checking all common ancestors and taking the minimum of dist(u, ancestor) + dist(v, ancestor). Total time: O(n log n + q log n).\n\n### Pattern 2: Counting Paths with a Given Property\n\n**Problem type:** Count the number of paths in a tree whose total weight equals k, or whose length (number of edges) is at most k.\n\n**How centroid decomposition helps:** At each centroid, gather all distances from the centroid to nodes in its subtree. Use a hash map or sorted array to count pairs that satisfy the property. Subtract pairs that are in the same child subtree (to avoid double counting). Recurse on each subtree.\n\n### Pattern 3: Closest Marked Node\n\n**Problem type:** Maintain a set of marked nodes that changes over time. Answer queries of the form \"what is the distance to the closest marked node from u?\"\n\n**How centroid decomposition helps:** For each centroid tree ancestor of u, maintain the minimum distance to any marked node in that ancestor's subtree. Updates and queries each walk O(log n) ancestors.\n\n### Interview Tips\n\n1. **Start by explaining the problem.** Before diving into centroid decomposition, clearly state why naive approaches are too slow. This shows you understand the problem before reaching for a tool.\n2. **Draw the centroid tree.** A quick sketch of a 5-7 node tree and its centroid tree makes the concept immediately clear to an interviewer. Seeing the O(log n) depth visually is much more convincing than a verbal explanation.\n3. **Emphasize the divide-and-conquer analogy.** Frame centroid decomposition as \"merge sort for trees.\" The centroid is a balanced pivot, and each level processes all n nodes. This resonates with interviewers who know sorting well.\n4. **Know the complexity proof.** Be ready to explain why the centroid tree has O(log n) depth (each subtree is at most n/2, so depth doubles at most log n times) and why total build time is O(n log n) (O(n) work per level, O(log n) levels).\n5. **Mention the key property.** Every path in the original tree passes through the LCA of its endpoints in the centroid tree. This is the core reason centroid decomposition works for path queries.\n\n---\n\n# Summary\n\n### Key Takeaways\n\n- The **centroid** of a tree is the node whose removal leaves no component larger than n/2. It always exists and can be found in O(n) time.\n- **Centroid decomposition** recursively finds and removes centroids, building a new tree (the centroid tree) with **O(log n) depth**. This is guaranteed because each subtree is at most half the parent's size.\n- The **build time is O(n log n)**: O(log n) levels of recursion, each processing all n nodes across all subproblems.\n- The **key property** is that every path in the original tree passes through the LCA of its endpoints in the centroid tree. This is why centroid decomposition enables efficient path queries.\n- For **distance queries**, precompute distances from each node to its O(log n) centroid tree ancestors, then answer each query in O(log n) by checking all common ancestor depths.\n- Centroid decomposition excels at **distance queries, path counting, and dynamic nearest-neighbor problems** on trees.\n\n### Quick Reference\n\n\n| Aspect | Details |\n|--------|---------|\n| **Build Time** | O(n log n) |\n| **Query Time** | O(log n) per distance query |\n| **Space** | O(n log n) for distance tables |\n| **Centroid Tree Depth** | O(log n) |\n| **Key Property** | Every original path passes through LCA in centroid tree |\n| **Best For** | Distance queries, path counting, closest marked node |\n| **Avoid When** | Subtree-only queries (use Euler tour), simple LCA (use sparse table) |\n","pageType":"dsa"}

Centroid Decomposition

Ashish Pratap Singh

Get Premium