{"title":"Heavy-Light Decomposition (HLD)","description":"","content":"You need to answer path queries on a tree, things like \"what is the maximum edge weight on the path from node A to node B?\" or \"add 5 to every node value along the path from X to Y.\" A segment tree handles these operations beautifully on arrays, but a tree is not an array. Paths twist and branch, and there is no obvious way to map them onto contiguous segments.\n\nHeavy-Light Decomposition solves this by cleverly flattening a tree into an array so that any path query can be answered in O(log^2 n) time. It is one of the most powerful techniques in competitive programming for tree path problems, and once you understand the core idea, it is far less intimidating than it sounds.\n\n---\n\n# Why Heavy-Light Decomposition Matters\n\nTree path queries with updates come up surprisingly often:\n\n- **Network routing.** Find the bottleneck (minimum bandwidth) on the path between two routers, or update the capacity of all links along a route.\n- **Competitive programming.** Problems like SPOJ QTREE, Codeforces tree path queries, and many contest problems require efficient path operations. HLD is one of the standard tools.\n- **Hierarchical data.** Any tree structure where you need aggregate information along paths between arbitrary nodes, from file systems to game trees.\n\nWithout HLD, a single path query takes O(n) in the worst case. With HLD and a segment tree, that drops to O(log^2 n).\n\n---\n\n# The Core Idea\n\n### The Problem\n\nSegment trees handle range queries and updates on arrays beautifully, but a tree is not an array. The path from node 2 to node 7 is not stored in consecutive positions anywhere, so you cannot just hand it to a segment tree.\n\nThe naive approach walks the path and aggregates values, costing O(path length) per query, which is O(n) for a skewed tree. With Q queries, that is O(nQ), far too slow when n and Q reach the hundreds of thousands.\n\n### The Key Insight\n\nAt every internal node, the edge to the child with the largest subtree is the \"heavy\" edge. All other edges are \"light.\" Heavy edges form long chains through the tree.\n\nThe critical property: **any root-to-leaf path crosses at most O(log n) light edges.** Each light edge leads to a child whose subtree is at most half the parent's (the heavy child got the larger half). The subtree size halves with every light edge, and you can only halve n about log n times.\n\nAny path between two nodes therefore breaks into at most O(log n) chain segments. Each chain is contiguous in the position array, so one segment tree query per chain gives O(log^2 n) total.\n\n### Visual Overview\n\n\n```mermaid\nflowchart TD\n subgraph Tree[\"Tree with Heavy and Light Edges\"]\n R[\"Root (1)\"]:::primary\n A[\"2\"]:::primary\n B[\"3\"]:::orange\n C[\"4\"]:::primary\n D[\"5\"]:::orange\n E[\"6\"]:::primary\n F[\"7\"]:::orange\n G[\"8\"]:::primary\n end\n\n R ==>|\"heavy\"| A\n R -->|\"light\"| B\n A ==>|\"heavy\"| C\n A -->|\"light\"| D\n C ==>|\"heavy\"| E\n C -->|\"light\"| F\n E ==>|\"heavy\"| G\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nThick arrows are heavy edges, thin arrows are light edges. Nodes 1-2-4-6-8 form one long heavy chain, while 3, 5, and 7 branch off through light edges.\n\n### The Analogy\n\nThink of it like a highway system. Heavy edges are highways, light edges are local roads. To get from town A to town B, you take a local road to the nearest highway, travel along highways (switching a few times), then take a local road to your destination. You never switch highways more than O(log n) times, because each detour onto a local road means entering a significantly smaller region of the network.\n\n---\n\n# How It Works\n\nHLD requires two DFS passes over the tree, followed by a segment tree built on the resulting position array.\n\n### Step 1: Compute Subtree Sizes and Identify Heavy Children\n\nThe first DFS computes subtree sizes. For each internal node, the child with the largest subtree becomes the **heavy child** (edge to it is heavy). All other edges are light. If two children tie, pick either.\n\n\n```mermaid\nflowchart TD\n subgraph DFS1[\"First DFS: Compute Subtree Sizes\"]\n S1[\"Node 1
size = 8
heavy child = 2\"]:::primary\n S2[\"Node 2
size = 5
heavy child = 4\"]:::primary\n S3[\"Node 3
size = 2
heavy child = 9\"]:::teal\n S4[\"Node 4
size = 3
heavy child = 6\"]:::primary\n S5[\"Node 5
size = 1\"]:::teal\n S6[\"Node 6
size = 2
heavy child = 8\"]:::primary\n S7[\"Node 7
size = 1\"]:::teal\n S8[\"Node 8
size = 1\"]:::primary\n S9[\"Node 9
size = 1\"]:::teal\n end\n\n S1 --> S2\n S1 --> S3\n S2 --> S4\n S2 --> S5\n S4 --> S6\n S4 --> S7\n S6 --> S8\n S3 --> S9\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n### Step 2: Assign Chain Heads and Positions\n\nThe second DFS traverses the tree again, **always visiting the heavy child first.** This ensures that heavy chain nodes get consecutive positions in the flattened array.\n\nEach node gets two things assigned:\n\n- **Chain head:** the topmost node in its heavy chain. Nodes reached via a light edge start a new chain (they are their own chain head). Nodes reached via a heavy edge inherit their parent's chain head.\n- **Position (pos):** its index in the flattened array. Since we visit heavy children first, all nodes in a chain get consecutive positions, which maps directly to segment tree range queries.\n\n### Step 3: Build the Segment Tree\n\nBuild a segment tree over the flattened position array. Each node's value goes at its assigned position. Range queries and updates now work on any contiguous segment.\n\n### Step 4: Answer Path Queries\n\nTo query the path from u to v:\n\n1. While u and v are on different chains (their chain heads differ):\n\n- Pick the node whose chain head is deeper (say it is u).\n- Query the segment tree for the range from head[u]'s position to u's position.\n- Move u up to the parent of head[u] (jumping to the chain above).\n\n1. Once u and v are on the same chain, query the segment tree for the range between their positions.\n\nThis \"climbing\" process visits at most O(log n) chains, and each segment tree query costs O(log n), giving O(log^2 n) total.\n\n\n```mermaid\nflowchart TD\n subgraph PathQuery[\"Path Query: Climbing Chains\"]\n Q1[\"u on Chain C\"]:::primary\n Q2[\"Query segment
head[u].pos to u.pos\"]:::teal\n Q3[\"Jump: u = parent(head[u])\"]:::orange\n Q4[\"u and v on
same chain?\"]:::orange\n Q5[\"Query segment
between u.pos and v.pos\"]:::green\n end\n\n Q1 --> Q2\n Q2 --> Q3\n Q3 --> Q4\n Q4 -->|\"No\"| Q1\n Q4 -->|\"Yes\"| Q5\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```\n\n\n---\n\n# Example Walkthrough\n\nLet us trace through a concrete 9-node tree.\n\n### The Tree\n\n\n```shell\n1\n / \\\n 2 3\n / \\ \\\n 4 5 9\n / \\\n 6 7\n |\n 8\n```\n\n\nNode values: `val = [_, 4, 2, 7, 3, 1, 5, 9, 6, 8]` (1-indexed, index 0 unused).\n\n### Step 1: Subtree Sizes and Heavy Children\n\nAfter the first DFS (rooted at node 1):\n\n\n| Node | Subtree Size | Children (sizes) | Heavy Child |\n|------|-------------|-------------------|-------------|\n| 1 | 9 | 2(6), 3(2) | 2 |\n| 2 | 6 | 4(4), 5(1) | 4 |\n| 3 | 2 | 9(1) | 9 |\n| 4 | 4 | 6(2), 7(1) | 6 |\n| 5 | 1 | (leaf) | - |\n| 6 | 2 | 8(1) | 8 |\n| 7 | 1 | (leaf) | - |\n| 8 | 1 | (leaf) | - |\n| 9 | 1 | (leaf) | - |\n\n\nHeavy edges: 1-2, 2-4, 4-6, 6-8, 3-9. Light edges: 1-3, 2-5, 4-7.\n\n### Step 2: Chain Formation and Position Assignment\n\nThe second DFS visits heavy children first. Starting from root 1:\n\n- **Chain 1 (head = 1):** 1 -> 2 -> 4 -> 6 -> 8 (all heavy edges)\n- **Chain 2 (head = 7):** 7 (light edge from 4, new chain)\n- **Chain 3 (head = 5):** 5 (light edge from 2, new chain)\n- **Chain 4 (head = 3):** 3 -> 9 (light edge from 1, then heavy to 9)\n\nPosition assignment:\n\n\n| Node | Chain Head | Position (pos) | Value at pos |\n|------|-----------|----------------|--------------|\n| 1 | 1 | 0 | 4 |\n| 2 | 1 | 1 | 2 |\n| 4 | 1 | 2 | 3 |\n| 6 | 1 | 3 | 5 |\n| 8 | 1 | 4 | 6 |\n| 7 | 7 | 5 | 9 |\n| 5 | 5 | 6 | 1 |\n| 3 | 3 | 7 | 7 |\n| 9 | 3 | 8 | 8 |\n\n\nThe flattened array for the segment tree is: `[4, 2, 3, 5, 6, 9, 1, 7, 8]`.\n\n\n```mermaid\nflowchart LR\n subgraph Chains[\"Heavy Chains Mapped to Array\"]\n P0[\"pos 0
node 1
val=4\"]:::primary\n P1[\"pos 1
node 2
val=2\"]:::primary\n P2[\"pos 2
node 4
val=3\"]:::primary\n P3[\"pos 3
node 6
val=5\"]:::primary\n P4[\"pos 4
node 8
val=6\"]:::primary\n P5[\"pos 5
node 7
val=9\"]:::orange\n P6[\"pos 6
node 5
val=1\"]:::orange\n P7[\"pos 7
node 3
val=7\"]:::teal\n P8[\"pos 8
node 9
val=8\"]:::teal\n end\n\n P0 --- P1 --- P2 --- P3 --- P4\n P7 --- P8\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\nChain 1 (cyan) occupies positions 0-4. Singleton chains 7 and 5 (orange) sit at positions 5-6. Chain 4 (teal) occupies 7-8. Each chain is contiguous.\n\n### Step 3: Path Query Example\n\nLet us compute the **path sum from node 8 to node 5**.\n\nThe path is: 8 -> 6 -> 4 -> 2 -> 5.\n\n\n```shell\nIteration 1:\n u = 8 (chain head = 1, depth = 4)\n v = 5 (chain head = 5, depth = 2)\n Different chains. Chain head of v (node 5) is deeper? depth[head[v]=5] = 2, depth[head[u]=1] = 0.\n v's chain head is deeper, so process v's chain.\n Query segment tree for range [pos[5], pos[5]] = [6, 6] -> value = 1\n Move v to parent of head[5] = parent of 5 = 2. Now v = 2.\n\nIteration 2:\n u = 8 (chain head = 1)\n v = 2 (chain head = 1)\n Same chain! Query range [pos[2], pos[8]] = [1, 4] -> values = 2 + 3 + 5 + 6 = 16\n (pos[2]=1 is smaller than pos[8]=4, so range is [1, 4])\n\nTotal sum = 1 + 16 = 17\n\nVerification: path 8->6->4->2->5, values = 6+5+3+2+1 = 17. Correct.\n```\n\n\nOnly 2 segment tree queries instead of visiting all 5 nodes. On larger trees, the savings are dramatic.\n\n---\n\n# Implementation\n\nComplete HLD with a segment tree for path sum queries and point updates on node values.\n\n\n```java\nimport java.util.*;\n\npublic class HeavyLightDecomposition {\n int n;\n List> adj;\n int[] parent, depth, subtreeSize, heavyChild;\n int[] chainHead, pos, nodeAtPos;\n int[] segTree;\n int posCounter;\n\n public HeavyLightDecomposition(int n) {\n this.n = n;\n adj = new ArrayList<>();\n for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());\n parent = new int[n + 1];\n depth = new int[n + 1];\n subtreeSize = new int[n + 1];\n heavyChild = new int[n + 1];\n chainHead = new int[n + 1];\n pos = new int[n + 1];\n nodeAtPos = new int[n + 1];\n segTree = new int[4 * (n + 1)];\n posCounter = 0;\n Arrays.fill(heavyChild, -1);\n }\n\n void dfs(int u, int par, int d) {\n parent[u] = par; depth[u] = d; subtreeSize[u] = 1;\n int maxChildSize = 0;\n for (int v : adj.get(u)) {\n if (v == par) continue;\n dfs(v, u, d + 1);\n subtreeSize[u] += subtreeSize[v];\n if (subtreeSize[v] > maxChildSize) {\n maxChildSize = subtreeSize[v];\n heavyChild[u] = v;\n }\n }\n }\n\n void decompose(int u, int head) {\n chainHead[u] = head;\n pos[u] = posCounter;\n nodeAtPos[posCounter++] = u;\n if (heavyChild[u] != -1) decompose(heavyChild[u], head);\n for (int v : adj.get(u)) {\n if (v == parent[u] || v == heavyChild[u]) continue;\n decompose(v, v);\n }\n }\n\n void build(int node, int start, int end, int[] values) {\n if (start == end) {\n segTree[node] = values[nodeAtPos[start]];\n return;\n }\n int mid = (start + end) / 2;\n build(2 * node, start, mid, values);\n build(2 * node + 1, mid + 1, end, values);\n segTree[node] = segTree[2 * node] + segTree[2 * node + 1];\n }\n\n void update(int node, int start, int end, int idx, int val) {\n if (start == end) {\n segTree[node] = val;\n return;\n }\n int mid = (start + end) / 2;\n if (idx <= mid) update(2 * node, start, mid, idx, val);\n else update(2 * node + 1, mid + 1, end, idx, val);\n segTree[node] = segTree[2 * node] + segTree[2 * node + 1];\n }\n\n int query(int node, int start, int end, int l, int r) {\n if (r < start || end < l) return 0;\n if (l <= start && end <= r) return segTree[node];\n int mid = (start + end) / 2;\n return query(2 * node, start, mid, l, r)\n + query(2 * node + 1, mid + 1, end, l, r);\n }\n\n int pathQuery(int u, int v) {\n int result = 0;\n while (chainHead[u] != chainHead[v]) {\n if (depth[chainHead[u]] < depth[chainHead[v]]) {\n int temp = u; u = v; v = temp;\n }\n result += query(1, 0, n - 1, pos[chainHead[u]], pos[u]);\n u = parent[chainHead[u]];\n }\n if (depth[u] > depth[v]) { int temp = u; u = v; v = temp; }\n result += query(1, 0, n - 1, pos[u], pos[v]);\n return result;\n }\n\n void pointUpdate(int u, int newVal) { update(1, 0, n - 1, pos[u], newVal); }\n\n void init(int root, int[] values) {\n dfs(root, 0, 0); decompose(root, root); build(1, 0, n - 1, values);\n }\n\n void addEdge(int u, int v) { adj.get(u).add(v); adj.get(v).add(u); }\n}\n```\n\n```python\nimport sys\nfrom collections import defaultdict\nsys.setrecursionlimit(300000)\n\nclass HeavyLightDecomposition:\n def __init__(self, n):\n self.n = n\n self.adj = defaultdict(list)\n self.parent = [0] * (n + 1)\n self.depth = [0] * (n + 1)\n self.subtree_size = [0] * (n + 1)\n self.heavy_child = [-1] * (n + 1)\n self.chain_head = [0] * (n + 1)\n self.pos = [0] * (n + 1)\n self.node_at_pos = [0] * (n + 1)\n self.seg_tree = [0] * (4 * (n + 1))\n self.pos_counter = 0\n\n def add_edge(self, u, v):\n self.adj[u].append(v)\n self.adj[v].append(u)\n\n def dfs(self, u, par, d):\n self.parent[u] = par\n self.depth[u] = d\n self.subtree_size[u] = 1\n max_child_size = 0\n for v in self.adj[u]:\n if v == par: continue\n self.dfs(v, u, d + 1)\n self.subtree_size[u] += self.subtree_size[v]\n if self.subtree_size[v] > max_child_size:\n max_child_size = self.subtree_size[v]\n self.heavy_child[u] = v\n\n def decompose(self, u, head):\n self.chain_head[u] = head\n self.pos[u] = self.pos_counter\n self.node_at_pos[self.pos_counter] = u\n self.pos_counter += 1\n if self.heavy_child[u] != -1:\n self.decompose(self.heavy_child[u], head) # heavy child first\n for v in self.adj[u]:\n if v == self.parent[u] or v == self.heavy_child[u]: continue\n self.decompose(v, v) # new chain\n\n def _build(self, node, start, end, values):\n if start == end:\n self.seg_tree[node] = values[self.node_at_pos[start]]\n return\n mid = (start + end) // 2\n self._build(2 * node, start, mid, values)\n self._build(2 * node + 1, mid + 1, end, values)\n self.seg_tree[node] = self.seg_tree[2 * node] + self.seg_tree[2 * node + 1]\n\n def _update(self, node, start, end, idx, val):\n if start == end:\n self.seg_tree[node] = val\n return\n mid = (start + end) // 2\n if idx <= mid: self._update(2 * node, start, mid, idx, val)\n else: self._update(2 * node + 1, mid + 1, end, idx, val)\n self.seg_tree[node] = self.seg_tree[2 * node] + self.seg_tree[2 * node + 1]\n\n def _query(self, node, start, end, l, r):\n if r < start or end < l: return 0\n if l <= start and end <= r: return self.seg_tree[node]\n mid = (start + end) // 2\n return (self._query(2 * node, start, mid, l, r)\n + self._query(2 * node + 1, mid + 1, end, l, r))\n\n def path_query(self, u, v):\n result = 0\n while self.chain_head[u] != self.chain_head[v]:\n if self.depth[self.chain_head[u]] < self.depth[self.chain_head[v]]:\n u, v = v, u\n result += self._query(1, 0, self.n - 1,\n self.pos[self.chain_head[u]], self.pos[u])\n u = self.parent[self.chain_head[u]]\n if self.depth[u] > self.depth[v]:\n u, v = v, u\n result += self._query(1, 0, self.n - 1, self.pos[u], self.pos[v])\n return result\n\n def point_update(self, u, new_val):\n self._update(1, 0, self.n - 1, self.pos[u], new_val)\n\n def init(self, root, values):\n self.dfs(root, 0, 0)\n self.decompose(root, root)\n self._build(1, 0, self.n - 1, values)\n```\n\n```cpp\n#include \n#include \nusing namespace std;\n\nclass HeavyLightDecomposition {\n int n, posCounter;\n vector> adj;\n vector parent, depth, subtreeSize, heavyChild;\n vector chainHead, pos, nodeAtPos, segTree;\n\n void dfs(int u, int par, int d) {\n parent[u] = par; depth[u] = d; subtreeSize[u] = 1;\n int maxChildSize = 0;\n for (int v : adj[u]) {\n if (v == par) continue;\n dfs(v, u, d + 1);\n subtreeSize[u] += subtreeSize[v];\n if (subtreeSize[v] > maxChildSize) {\n maxChildSize = subtreeSize[v];\n heavyChild[u] = v;\n }\n }\n }\n\n void decompose(int u, int head) {\n chainHead[u] = head;\n pos[u] = posCounter;\n nodeAtPos[posCounter++] = u;\n if (heavyChild[u] != -1) decompose(heavyChild[u], head);\n for (int v : adj[u]) {\n if (v == parent[u] || v == heavyChild[u]) continue;\n decompose(v, v);\n }\n }\n\n void build(int node, int s, int e, vector& val) {\n if (s == e) { segTree[node] = val[nodeAtPos[s]]; return; }\n int m = (s + e) / 2;\n build(2*node, s, m, val); build(2*node+1, m+1, e, val);\n segTree[node] = segTree[2*node] + segTree[2*node+1];\n }\n\n void update(int node, int s, int e, int idx, int v) {\n if (s == e) { segTree[node] = v; return; }\n int m = (s + e) / 2;\n if (idx <= m) update(2*node, s, m, idx, v);\n else update(2*node+1, m+1, e, idx, v);\n segTree[node] = segTree[2*node] + segTree[2*node+1];\n }\n\n int query(int node, int s, int e, int l, int r) {\n if (r < s || e < l) return 0;\n if (l <= s && e <= r) return segTree[node];\n int m = (s + e) / 2;\n return query(2*node, s, m, l, r) + query(2*node+1, m+1, e, l, r);\n }\n\npublic:\n HeavyLightDecomposition(int n) : n(n), posCounter(0), adj(n+1),\n parent(n+1), depth(n+1), subtreeSize(n+1), heavyChild(n+1, -1),\n chainHead(n+1), pos(n+1), nodeAtPos(n+1), segTree(4*(n+1), 0) {}\n\n void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); }\n\n void init(int root, vector& values) {\n dfs(root, 0, 0); decompose(root, root); build(1, 0, n-1, values);\n }\n\n int pathQuery(int u, int v) {\n int result = 0;\n while (chainHead[u] != chainHead[v]) {\n if (depth[chainHead[u]] < depth[chainHead[v]]) swap(u, v);\n result += query(1, 0, n-1, pos[chainHead[u]], pos[u]);\n u = parent[chainHead[u]];\n }\n if (depth[u] > depth[v]) swap(u, v);\n result += query(1, 0, n-1, pos[u], pos[v]);\n return result;\n }\n\n void pointUpdate(int u, int newVal) { update(1, 0, n-1, pos[u], newVal); }\n};\n```\n\n```csharp\nusing System;\nusing System.Collections.Generic;\n\npublic class HeavyLightDecomposition {\n int n;\n List> adj;\n int[] parent, depth, subtreeSize, heavyChild;\n int[] chainHead, pos, nodeAtPos;\n int[] segTree;\n int posCounter;\n\n public HeavyLightDecomposition(int n) {\n this.n = n;\n adj = new List>();\n for (int i = 0; i <= n; i++) adj.Add(new List());\n parent = new int[n + 1];\n depth = new int[n + 1];\n subtreeSize = new int[n + 1];\n heavyChild = new int[n + 1];\n chainHead = new int[n + 1];\n pos = new int[n + 1];\n nodeAtPos = new int[n + 1];\n segTree = new int[4 * (n + 1)];\n posCounter = 0;\n for (int i = 0; i <= n; i++) heavyChild[i] = -1;\n }\n\n void Dfs(int u, int par, int d) {\n parent[u] = par; depth[u] = d; subtreeSize[u] = 1;\n int maxChildSize = 0;\n foreach (int v in adj[u]) {\n if (v == par) continue;\n Dfs(v, u, d + 1);\n subtreeSize[u] += subtreeSize[v];\n if (subtreeSize[v] > maxChildSize) {\n maxChildSize = subtreeSize[v];\n heavyChild[u] = v;\n }\n }\n }\n\n void Decompose(int u, int head) {\n chainHead[u] = head;\n pos[u] = posCounter;\n nodeAtPos[posCounter++] = u;\n if (heavyChild[u] != -1) Decompose(heavyChild[u], head);\n foreach (int v in adj[u]) {\n if (v == parent[u] || v == heavyChild[u]) continue;\n Decompose(v, v);\n }\n }\n\n void Build(int node, int start, int end, int[] values) {\n if (start == end) {\n segTree[node] = values[nodeAtPos[start]];\n return;\n }\n int mid = (start + end) / 2;\n Build(2 * node, start, mid, values);\n Build(2 * node + 1, mid + 1, end, values);\n segTree[node] = segTree[2 * node] + segTree[2 * node + 1];\n }\n\n void Update(int node, int start, int end, int idx, int val) {\n if (start == end) {\n segTree[node] = val;\n return;\n }\n int mid = (start + end) / 2;\n if (idx <= mid) Update(2 * node, start, mid, idx, val);\n else Update(2 * node + 1, mid + 1, end, idx, val);\n segTree[node] = segTree[2 * node] + segTree[2 * node + 1];\n }\n\n int Query(int node, int start, int end, int l, int r) {\n if (r < start || end < l) return 0;\n if (l <= start && end <= r) return segTree[node];\n int mid = (start + end) / 2;\n return Query(2 * node, start, mid, l, r)\n + Query(2 * node + 1, mid + 1, end, l, r);\n }\n\n public int PathQuery(int u, int v) {\n int result = 0;\n while (chainHead[u] != chainHead[v]) {\n if (depth[chainHead[u]] < depth[chainHead[v]]) {\n int temp = u; u = v; v = temp;\n }\n result += Query(1, 0, n - 1, pos[chainHead[u]], pos[u]);\n u = parent[chainHead[u]];\n }\n if (depth[u] > depth[v]) { int temp = u; u = v; v = temp; }\n result += Query(1, 0, n - 1, pos[u], pos[v]);\n return result;\n }\n\n public void PointUpdate(int u, int newVal) { Update(1, 0, n - 1, pos[u], newVal); }\n\n public void Init(int root, int[] values) {\n Dfs(root, 0, 0); Decompose(root, root); Build(1, 0, n - 1, values);\n }\n\n public void AddEdge(int u, int v) { adj[u].Add(v); adj[v].Add(u); }\n}\n```\n\n```go\npackage main\n\ntype HeavyLightDecomposition struct {\n n int\n adj [][]int\n parent []int\n depth []int\n subtreeSize []int\n heavyChild []int\n chainHead []int\n pos []int\n nodeAtPos []int\n segTree []int\n posCounter int\n}\n\nfunc NewHeavyLightDecomposition(n int) *HeavyLightDecomposition {\n h := &HeavyLightDecomposition{\n n: n,\n adj: make([][]int, n+1),\n parent: make([]int, n+1),\n depth: make([]int, n+1),\n subtreeSize: make([]int, n+1),\n heavyChild: make([]int, n+1),\n chainHead: make([]int, n+1),\n pos: make([]int, n+1),\n nodeAtPos: make([]int, n+1),\n segTree: make([]int, 4*(n+1)),\n posCounter: 0,\n }\n for i := 0; i <= n; i++ {\n h.heavyChild[i] = -1\n }\n return h\n}\n\nfunc (h *HeavyLightDecomposition) AddEdge(u, v int) {\n h.adj[u] = append(h.adj[u], v)\n h.adj[v] = append(h.adj[v], u)\n}\n\nfunc (h *HeavyLightDecomposition) dfs(u, par, d int) {\n h.parent[u] = par\n h.depth[u] = d\n h.subtreeSize[u] = 1\n maxChildSize := 0\n for _, v := range h.adj[u] {\n if v == par {\n continue\n }\n h.dfs(v, u, d+1)\n h.subtreeSize[u] += h.subtreeSize[v]\n if h.subtreeSize[v] > maxChildSize {\n maxChildSize = h.subtreeSize[v]\n h.heavyChild[u] = v\n }\n }\n}\n\nfunc (h *HeavyLightDecomposition) decompose(u, head int) {\n h.chainHead[u] = head\n h.pos[u] = h.posCounter\n h.nodeAtPos[h.posCounter] = u\n h.posCounter++\n if h.heavyChild[u] != -1 {\n h.decompose(h.heavyChild[u], head)\n }\n for _, v := range h.adj[u] {\n if v == h.parent[u] || v == h.heavyChild[u] {\n continue\n }\n h.decompose(v, v)\n }\n}\n\nfunc (h *HeavyLightDecomposition) build(node, start, end int, values []int) {\n if start == end {\n h.segTree[node] = values[h.nodeAtPos[start]]\n return\n }\n mid := (start + end) / 2\n h.build(2*node, start, mid, values)\n h.build(2*node+1, mid+1, end, values)\n h.segTree[node] = h.segTree[2*node] + h.segTree[2*node+1]\n}\n\nfunc (h *HeavyLightDecomposition) update(node, start, end, idx, val int) {\n if start == end {\n h.segTree[node] = val\n return\n }\n mid := (start + end) / 2\n if idx <= mid {\n h.update(2*node, start, mid, idx, val)\n } else {\n h.update(2*node+1, mid+1, end, idx, val)\n }\n h.segTree[node] = h.segTree[2*node] + h.segTree[2*node+1]\n}\n\nfunc (h *HeavyLightDecomposition) query(node, start, end, l, r int) int {\n if r < start || end < l {\n return 0\n }\n if l <= start && end <= r {\n return h.segTree[node]\n }\n mid := (start + end) / 2\n return h.query(2*node, start, mid, l, r) +\n h.query(2*node+1, mid+1, end, l, r)\n}\n\nfunc (h *HeavyLightDecomposition) PathQuery(u, v int) int {\n result := 0\n for h.chainHead[u] != h.chainHead[v] {\n if h.depth[h.chainHead[u]] < h.depth[h.chainHead[v]] {\n u, v = v, u\n }\n result += h.query(1, 0, h.n-1, h.pos[h.chainHead[u]], h.pos[u])\n u = h.parent[h.chainHead[u]]\n }\n if h.depth[u] > h.depth[v] {\n u, v = v, u\n }\n result += h.query(1, 0, h.n-1, h.pos[u], h.pos[v])\n return result\n}\n\nfunc (h *HeavyLightDecomposition) PointUpdate(u, newVal int) {\n h.update(1, 0, h.n-1, h.pos[u], newVal)\n}\n\nfunc (h *HeavyLightDecomposition) Init(root int, values []int) {\n h.dfs(root, 0, 0)\n h.decompose(root, root)\n h.build(1, 0, h.n-1, values)\n}\n```\n\n```rust\npub struct HeavyLightDecomposition {\n n: usize,\n adj: Vec>,\n parent: Vec,\n depth: Vec,\n subtree_size: Vec,\n heavy_child: Vec,\n chain_head: Vec,\n pos: Vec,\n node_at_pos: Vec,\n seg_tree: Vec,\n pos_counter: usize,\n}\n\nimpl HeavyLightDecomposition {\n pub fn new(n: usize) -> Self {\n HeavyLightDecomposition {\n n,\n adj: vec![Vec::new(); n + 1],\n parent: vec![0; n + 1],\n depth: vec![0; n + 1],\n subtree_size: vec![0; n + 1],\n heavy_child: vec![-1; n + 1],\n chain_head: vec![0; n + 1],\n pos: vec![0; n + 1],\n node_at_pos: vec![0; n + 1],\n seg_tree: vec![0; 4 * (n + 1)],\n pos_counter: 0,\n }\n }\n\n pub fn add_edge(&mut self, u: usize, v: usize) {\n self.adj[u].push(v);\n self.adj[v].push(u);\n }\n\n fn dfs(&mut self, u: usize, par: usize, d: usize) {\n self.parent[u] = par;\n self.depth[u] = d;\n self.subtree_size[u] = 1;\n let mut max_child_size = 0;\n let children = self.adj[u].clone();\n for v in children {\n if v == par {\n continue;\n }\n self.dfs(v, u, d + 1);\n self.subtree_size[u] += self.subtree_size[v];\n if self.subtree_size[v] > max_child_size {\n max_child_size = self.subtree_size[v];\n self.heavy_child[u] = v as i64;\n }\n }\n }\n\n fn decompose(&mut self, u: usize, head: usize) {\n self.chain_head[u] = head;\n self.pos[u] = self.pos_counter;\n self.node_at_pos[self.pos_counter] = u;\n self.pos_counter += 1;\n if self.heavy_child[u] != -1 {\n self.decompose(self.heavy_child[u] as usize, head);\n }\n let children = self.adj[u].clone();\n for v in children {\n if v == self.parent[u] || (self.heavy_child[u] != -1 && v == self.heavy_child[u] as usize) {\n continue;\n }\n self.decompose(v, v);\n }\n }\n\n fn build(&mut self, node: usize, start: usize, end: usize, values: &[i64]) {\n if start == end {\n self.seg_tree[node] = values[self.node_at_pos[start]];\n return;\n }\n let mid = (start + end) / 2;\n self.build(2 * node, start, mid, values);\n self.build(2 * node + 1, mid + 1, end, values);\n self.seg_tree[node] = self.seg_tree[2 * node] + self.seg_tree[2 * node + 1];\n }\n\n fn update(&mut self, node: usize, start: usize, end: usize, idx: usize, val: i64) {\n if start == end {\n self.seg_tree[node] = val;\n return;\n }\n let mid = (start + end) / 2;\n if idx <= mid {\n self.update(2 * node, start, mid, idx, val);\n } else {\n self.update(2 * node + 1, mid + 1, end, idx, val);\n }\n self.seg_tree[node] = self.seg_tree[2 * node] + self.seg_tree[2 * node + 1];\n }\n\n fn query(&self, node: usize, start: usize, end: usize, l: usize, r: usize) -> i64 {\n if r < start || end < l {\n return 0;\n }\n if l <= start && end <= r {\n return self.seg_tree[node];\n }\n let mid = (start + end) / 2;\n self.query(2 * node, start, mid, l, r)\n + self.query(2 * node + 1, mid + 1, end, l, r)\n }\n\n pub fn path_query(&self, mut u: usize, mut v: usize) -> i64 {\n let mut result = 0;\n while self.chain_head[u] != self.chain_head[v] {\n if self.depth[self.chain_head[u]] < self.depth[self.chain_head[v]] {\n std::mem::swap(&mut u, &mut v);\n }\n result += self.query(1, 0, self.n - 1, self.pos[self.chain_head[u]], self.pos[u]);\n u = self.parent[self.chain_head[u]];\n }\n if self.depth[u] > self.depth[v] {\n std::mem::swap(&mut u, &mut v);\n }\n result += self.query(1, 0, self.n - 1, self.pos[u], self.pos[v]);\n result\n }\n\n pub fn point_update(&mut self, u: usize, new_val: i64) {\n self.update(1, 0, self.n - 1, self.pos[u], new_val);\n }\n\n pub fn init(&mut self, root: usize, values: &[i64]) {\n self.dfs(root, 0, 0);\n self.decompose(root, root);\n self.build(1, 0, self.n - 1, values);\n }\n}\n```\n\n```javascript\nclass HeavyLightDecomposition {\n constructor(n) {\n this.n = n;\n this.adj = [];\n for (let i = 0; i <= n; i++) this.adj.push([]);\n this.parent = new Array(n + 1).fill(0);\n this.depth = new Array(n + 1).fill(0);\n this.subtreeSize = new Array(n + 1).fill(0);\n this.heavyChild = new Array(n + 1).fill(-1);\n this.chainHead = new Array(n + 1).fill(0);\n this.pos = new Array(n + 1).fill(0);\n this.nodeAtPos = new Array(n + 1).fill(0);\n this.segTree = new Array(4 * (n + 1)).fill(0);\n this.posCounter = 0;\n }\n\n addEdge(u, v) {\n this.adj[u].push(v);\n this.adj[v].push(u);\n }\n\n dfs(u, par, d) {\n this.parent[u] = par;\n this.depth[u] = d;\n this.subtreeSize[u] = 1;\n let maxChildSize = 0;\n for (const v of this.adj[u]) {\n if (v === par) continue;\n this.dfs(v, u, d + 1);\n this.subtreeSize[u] += this.subtreeSize[v];\n if (this.subtreeSize[v] > maxChildSize) {\n maxChildSize = this.subtreeSize[v];\n this.heavyChild[u] = v;\n }\n }\n }\n\n decompose(u, head) {\n this.chainHead[u] = head;\n this.pos[u] = this.posCounter;\n this.nodeAtPos[this.posCounter++] = u;\n if (this.heavyChild[u] !== -1) this.decompose(this.heavyChild[u], head);\n for (const v of this.adj[u]) {\n if (v === this.parent[u] || v === this.heavyChild[u]) continue;\n this.decompose(v, v);\n }\n }\n\n build(node, start, end, values) {\n if (start === end) {\n this.segTree[node] = values[this.nodeAtPos[start]];\n return;\n }\n const mid = Math.floor((start + end) / 2);\n this.build(2 * node, start, mid, values);\n this.build(2 * node + 1, mid + 1, end, values);\n this.segTree[node] = this.segTree[2 * node] + this.segTree[2 * node + 1];\n }\n\n update(node, start, end, idx, val) {\n if (start === end) {\n this.segTree[node] = val;\n return;\n }\n const mid = Math.floor((start + end) / 2);\n if (idx <= mid) this.update(2 * node, start, mid, idx, val);\n else this.update(2 * node + 1, mid + 1, end, idx, val);\n this.segTree[node] = this.segTree[2 * node] + this.segTree[2 * node + 1];\n }\n\n query(node, start, end, l, r) {\n if (r < start || end < l) return 0;\n if (l <= start && end <= r) return this.segTree[node];\n const mid = Math.floor((start + end) / 2);\n return this.query(2 * node, start, mid, l, r)\n + this.query(2 * node + 1, mid + 1, end, l, r);\n }\n\n pathQuery(u, v) {\n let result = 0;\n while (this.chainHead[u] !== this.chainHead[v]) {\n if (this.depth[this.chainHead[u]] < this.depth[this.chainHead[v]]) {\n [u, v] = [v, u];\n }\n result += this.query(1, 0, this.n - 1, this.pos[this.chainHead[u]], this.pos[u]);\n u = this.parent[this.chainHead[u]];\n }\n if (this.depth[u] > this.depth[v]) [u, v] = [v, u];\n result += this.query(1, 0, this.n - 1, this.pos[u], this.pos[v]);\n return result;\n }\n\n pointUpdate(u, newVal) {\n this.update(1, 0, this.n - 1, this.pos[u], newVal);\n }\n\n init(root, values) {\n this.dfs(root, 0, 0);\n this.decompose(root, root);\n this.build(1, 0, this.n - 1, values);\n }\n}\n```\n\n```typescript\nclass HeavyLightDecomposition {\n private n: number;\n private adj: number[][];\n private parent: number[];\n private depth: number[];\n private subtreeSize: number[];\n private heavyChild: number[];\n private chainHead: number[];\n private pos: number[];\n private nodeAtPos: number[];\n private segTree: number[];\n private posCounter: number;\n\n constructor(n: number) {\n this.n = n;\n this.adj = [];\n for (let i = 0; i <= n; i++) this.adj.push([]);\n this.parent = new Array(n + 1).fill(0);\n this.depth = new Array(n + 1).fill(0);\n this.subtreeSize = new Array(n + 1).fill(0);\n this.heavyChild = new Array(n + 1).fill(-1);\n this.chainHead = new Array(n + 1).fill(0);\n this.pos = new Array(n + 1).fill(0);\n this.nodeAtPos = new Array(n + 1).fill(0);\n this.segTree = new Array(4 * (n + 1)).fill(0);\n this.posCounter = 0;\n }\n\n addEdge(u: number, v: number): void {\n this.adj[u].push(v);\n this.adj[v].push(u);\n }\n\n private dfs(u: number, par: number, d: number): void {\n this.parent[u] = par;\n this.depth[u] = d;\n this.subtreeSize[u] = 1;\n let maxChildSize = 0;\n for (const v of this.adj[u]) {\n if (v === par) continue;\n this.dfs(v, u, d + 1);\n this.subtreeSize[u] += this.subtreeSize[v];\n if (this.subtreeSize[v] > maxChildSize) {\n maxChildSize = this.subtreeSize[v];\n this.heavyChild[u] = v;\n }\n }\n }\n\n private decompose(u: number, head: number): void {\n this.chainHead[u] = head;\n this.pos[u] = this.posCounter;\n this.nodeAtPos[this.posCounter++] = u;\n if (this.heavyChild[u] !== -1) this.decompose(this.heavyChild[u], head);\n for (const v of this.adj[u]) {\n if (v === this.parent[u] || v === this.heavyChild[u]) continue;\n this.decompose(v, v);\n }\n }\n\n private build(node: number, start: number, end: number, values: number[]): void {\n if (start === end) {\n this.segTree[node] = values[this.nodeAtPos[start]];\n return;\n }\n const mid = Math.floor((start + end) / 2);\n this.build(2 * node, start, mid, values);\n this.build(2 * node + 1, mid + 1, end, values);\n this.segTree[node] = this.segTree[2 * node] + this.segTree[2 * node + 1];\n }\n\n private update(node: number, start: number, end: number, idx: number, val: number): void {\n if (start === end) {\n this.segTree[node] = val;\n return;\n }\n const mid = Math.floor((start + end) / 2);\n if (idx <= mid) this.update(2 * node, start, mid, idx, val);\n else this.update(2 * node + 1, mid + 1, end, idx, val);\n this.segTree[node] = this.segTree[2 * node] + this.segTree[2 * node + 1];\n }\n\n private query(node: number, start: number, end: number, l: number, r: number): number {\n if (r < start || end < l) return 0;\n if (l <= start && end <= r) return this.segTree[node];\n const mid = Math.floor((start + end) / 2);\n return this.query(2 * node, start, mid, l, r)\n + this.query(2 * node + 1, mid + 1, end, l, r);\n }\n\n pathQuery(u: number, v: number): number {\n let result = 0;\n while (this.chainHead[u] !== this.chainHead[v]) {\n if (this.depth[this.chainHead[u]] < this.depth[this.chainHead[v]]) {\n [u, v] = [v, u];\n }\n result += this.query(1, 0, this.n - 1, this.pos[this.chainHead[u]], this.pos[u]);\n u = this.parent[this.chainHead[u]];\n }\n if (this.depth[u] > this.depth[v]) [u, v] = [v, u];\n result += this.query(1, 0, this.n - 1, this.pos[u], this.pos[v]);\n return result;\n }\n\n pointUpdate(u: number, newVal: number): void {\n this.update(1, 0, this.n - 1, this.pos[u], newVal);\n }\n\n init(root: number, values: number[]): void {\n this.dfs(root, 0, 0);\n this.decompose(root, root);\n this.build(1, 0, this.n - 1, values);\n }\n}\n```\n\n\n---\n\n# Code Explanation\n\nLet us walk through the key parts of the implementation.\n\n### The Two DFS Passes\n\nThe `dfs` function computes subtree sizes and identifies heavy children via standard post-order traversal. The `decompose` function is where the magic happens: it assigns positions and chain heads. The critical detail is that **the heavy child is always visited first**, ensuring the entire chain gets consecutive positions. Light children are visited afterward, each starting a new chain.\n\n### The Path Query Logic\n\nThe `pathQuery` function climbs from both endpoints toward their LCA, chain by chain:\n\n1. Compare the chain heads of u and v. Process the one whose chain head is **deeper** first.\n2. Query the segment tree for the range from that chain head's position to the node's position.\n3. Jump to the parent of the chain head, moving to the chain above.\n4. Once both nodes share the same chain head, do one final query between their positions.\n\n### Common Mistakes\n\n- **Forgetting to visit the heavy child first in the second DFS.** Without this, chain nodes will not get consecutive positions.\n- **Inconsistent indexing.** Tree nodes are 1-indexed, positions are 0-indexed. Pick a convention and stick with it.\n- **Stack overflow on deep trees.** For n up to 200,000, use iterative DFS or increase stack size (Java: thread with larger stack; Python: `sys.setrecursionlimit`).\n- **Wrong depth comparison.** Compare depths of **chain heads**, not the nodes themselves, when deciding which chain to climb.\n\n---\n\n# Complexity Analysis\n\n### Time Complexity\n\n**Preprocessing:** O(n)\n\n- First DFS: O(n) to compute subtree sizes.\n- Second DFS: O(n) to assign positions and chain heads.\n- Building the segment tree: O(n).\n\n**Per query or update:** O(log^2 n)\n\nAny path crosses at most O(log n) light edges (each halves the subtree size), so you switch chains at most O(log n) times. Each switch triggers one segment tree query costing O(log n), giving **O(log^2 n)** total. With a Fenwick tree for commutative operations, the asymptotic bound is the same but constant factors are smaller.\n\n### Space Complexity\n\n**Overall:** O(n) for all arrays (parent, depth, subtree size, chain head, position) plus O(4n) for the segment tree.\n\n\n| Operation | Time Complexity | Notes |\n|-----------|----------------|-------|\n| Preprocessing | O(n) | Two DFS + segment tree build |\n| Path query | O(log^2 n) | O(log n) chains, O(log n) per query |\n| Path update (point) | O(log^2 n) | Same chain traversal + seg tree update |\n| Path update (range) | O(log^2 n) | With lazy propagation on segment tree |\n| LCA query | O(log n) | Falls out of the chain climbing process |\n\n\n---\n\n# Variations and Extensions\n\n### Variation 1: Edge Values Instead of Node Values\n\nMany problems assign values to edges, not nodes. The trick is to push each edge's value down to the child node. Since every node except the root has exactly one parent edge, this mapping is unique. The only subtlety: in the final step when both nodes share a chain, exclude the LCA node (it holds its parent edge's value, not a path edge). The query range becomes `[pos[u] + 1, pos[v]]` instead of `[pos[u], pos[v]]`.\n\n### Variation 2: Subtree Queries\n\nHLD's position assignment gives a useful bonus: all nodes in a subtree get consecutive positions. The subtree of node u occupies `[pos[u], pos[u] + subtreeSize[u] - 1]`. Subtree queries reduce to a single segment tree range query, no chain climbing needed.\n\n### Variation 3: Lazy Propagation for Path Range Updates\n\nTo update all nodes on a path (e.g., add delta from u to v), use a segment tree with lazy propagation. The chain climbing is the same, but you perform range updates instead of queries. Each costs O(log n), so the total remains O(log^2 n).\n\n### Comparison Table\n\n\n| Variant | Modification | Use Case |\n|---------|-------------|----------|\n| Node values (standard) | Values stored at nodes | Path sum, path max |\n| Edge values | Push edge value to child node, exclude LCA in final query | Weighted trees, edge weight queries |\n| Subtree queries | Use `[pos[u], pos[u]+size[u]-1]` range | Subtree sum, subtree update |\n| Path range updates | Add lazy propagation to segment tree | Increment all nodes on a path |\n\n\n---\n\n# Comparison with Related Structures\n\n\n| Technique | Path Query | Path Update | Subtree Query | Complexity per Op | Difficulty |\n|-----------|-----------|-------------|---------------|-------------------|------------|\n| **HLD + Segment Tree** | Yes | Yes | Yes | O(log^2 n) | Medium |\n| **Euler Tour + Segment Tree** | Partial | Partial | Yes | O(log n) | Easy |\n| **Centroid Decomposition** | Yes (offline) | No (easily) | No | O(n log n) build, O(log n) query | Medium |\n| **Link-Cut Trees** | Yes | Yes | No | O(log n) amortized | Hard |\n\n\n### When to Choose HLD\n\n- You need both path queries **and** path updates on a static tree.\n- You need non-commutative operations (like path max/min with lazy updates).\n- You also need subtree queries (HLD gives this for free).\n\n### When NOT to Use HLD\n\n- **Dynamic trees** (edges added/removed). Use Link-Cut Trees instead.\n- **Subtree queries only.** Euler tour + segment tree is simpler at O(log n).\n- **Small trees** (n < 1000). Brute-force path traversal is fine.\n\n---\n\n# Common Patterns and Applications\n\n### Pattern 1: Path Aggregate Queries\n\n**Problem type:** Sum/max/min of values along the path from u to v. **How HLD helps:** Decompose the path into O(log n) chain segments, query the segment tree for each, combine results.\n\n### Pattern 2: Path Updates with Range Queries\n\n**Problem type:** Add delta to every node on a path, then query sums along other paths or subtrees. **How HLD helps:** Segment tree with lazy propagation. Path update decomposes into O(log n) range updates.\n\n### Pattern 3: LCA via HLD\n\n**Problem type:** Find the Lowest Common Ancestor of two nodes. **How HLD helps:** Chain climbing naturally finds the LCA. When u and v share a chain, the shallower node is the LCA. O(log n) with no extra preprocessing.\n\n### Interview Tips\n\n1. **Know the building blocks.** HLD combines DFS, segment trees, and LCA. Implement each cleanly before attempting HLD.\n2. **Start with the two-DFS framework.** Sketch the high-level approach first, then fill in details.\n3. **Explain the log n chain bound.** Each light edge halves subtree size. This is the core efficiency argument.\n4. **Practice the swap logic.** Compare depths of chain heads, not the nodes themselves.\n5. **Mention trade-offs.** HLD is simpler with better constants than Link-Cut Trees for static trees.\n\n---\n\n# Summary\n\n### Key Takeaways\n\n- HLD flattens a tree so any path decomposes into O(log n) contiguous chain segments.\n- Heavy edge = edge to child with largest subtree. Any root-to-leaf path crosses at most O(log n) light edges.\n- Two DFS passes: first computes sizes and heavy children, second assigns positions (heavy child first).\n- Path queries cost O(log^2 n): O(log n) chains times O(log n) per segment tree query.\n- LCA is a free byproduct of the chain climbing process.\n\n### Quick Reference\n\n\n| Aspect | Details |\n|--------|---------|\n| **Preprocessing Time** | O(n) |\n| **Path Query/Update** | O(log^2 n) with segment tree |\n| **Subtree Query** | O(log n) (contiguous positions) |\n| **Space** | O(n) |\n| **Prerequisites** | Segment tree, DFS, tree basics |\n| **Best For** | Path queries/updates on static trees |\n| **Avoid When** | Dynamic trees (use Link-Cut Trees), small n, subtree-only queries |\n","pageType":"dsa"}

Heavy-Light Decomposition (HLD)

Ashish Pratap Singh

Get Premium