Point decomposition, also known as centroid decomposition, is a powerful technique for efficiently solving path-related problems on trees. By recursively splitting the tree around its centroid, it ensures logarithmic depth of recursion, leading to optimal time complexity for many tree queries.
The algorithm follows three core steps:
- Find the centroid of the current subtree — the node whose removal splits the tree into components, each with size at most half of the original.
- Compute the contribution of all paths passing through this centroid.
- Remove the centroid and recursively process each resulting connected component.
Since the centroid guarantees that each recursive call operates on a subtree of size at most n/2, the recursion depth is bounded by O(log n). At each level, processing all nodes takes O(n) time, yielding an overall complexity of O(n log n).
There are two primary strategies to compute path contributions:
- Include-all-then-subtract: Count all valid paths through the centroid, then subtract those entirely contained within a single child subtree to avoid overcounting.
- Incremental accumulation: Process each child subtree one at a time, querying existing path data before updating the data structure with the current subtree’s paths.
Data structures such as Fenwick trees, segment trees, or hash maps are often used to efficiently maintain and query path statistics like distance counts or minimum edge counts.
Problem 1: Counting Paths with Weight ≤ K
We use the first method: collect all distances from the centroid to every node, sort them, and use two pointers to count valid pairs whose sum is ≤ K. Then subtract paths lying entirely within a single subtree to correct for overcounting.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 100010;
struct Edge {
int to, weight, next;
} edges[MAXN << 1];
int head[MAXN], edgeCount;
int n, target, ans;
int size[MAXN], dist[MAXN], centroid, minSubtreeSize;
int tempDist[MAXN], tempCount;
bool visited[MAXN];
void addEdge(int u, int v, int w) {
edges[++edgeCount] = {v, w, head[u]};
head[u] = edgeCount;
}
void findCentroid(int u, int parent, int totalNodes) {
size[u] = 1;
int maxSubtree = 0;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == parent || visited[v]) continue;
findCentroid(v, u, totalNodes);
size[u] += size[v];
maxSubtree = max(maxSubtree, size[v]);
}
maxSubtree = max(maxSubtree, totalNodes - size[u]);
if (maxSubtree < minSubtreeSize) {
minSubtreeSize = maxSubtree;
centroid = u;
}
}
void collectDistances(int u, int parent, int d) {
tempDist[++tempCount] = d;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == parent || visited[v]) continue;
collectDistances(v, u, d + edges[i].weight);
}
}
void countValidPairs(int sign) {
sort(tempDist + 1, tempDist + tempCount + 1);
int left = 0, validPairs = 0;
for (int right = tempCount; right > 0; --right) {
while (left < tempCount && tempDist[left + 1] + tempDist[right] <= target) ++left;
validPairs += left - (left >= right);
}
ans += (validPairs / 2) * sign;
}
void decompose(int u, int parent, int totalNodes) {
minSubtreeSize = totalNodes - 1;
centroid = u;
tempCount = 0;
findCentroid(u, parent, totalNodes);
visited[centroid] = true;
collectDistances(centroid, 0, 0);
countValidPairs(1);
for (int i = head[centroid]; i; i = edges[i].next) {
int child = edges[i].to;
if (child == parent || visited[child]) continue;
tempCount = 0;
collectDistances(child, centroid, edges[i].weight);
countValidPairs(-1);
}
for (int i = head[centroid]; i; i = edges[i].next) {
int child = edges[i].to;
if (child == parent || visited[child]) continue;
decompose(child, centroid, size[child]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i < n; ++i) {
int x, y, w;
cin >> x >> y >> w;
addEdge(x, y, w);
addEdge(y, x, w);
}
cin >> target;
decompose(1, 0, n);
cout << ans << '\n';
return 0;
}
Problem 2: Minimum Edge Count for Path Sum Exactly K
Here we use the second method: for each subtree, query existing distances to find a complementary path that sums to exactly K, then update the global answer with the minimum number of edges.
A key insight: when processing a subtree, we must first query the global count of distances before updating it. This ensures we don’t count paths that originate and end within the same subtree.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1000010;
const int INF = 0x3f3f3f3f;
struct Edge {
int to, weight, next;
} edges[MAXN << 1];
int head[MAXN], edgeCount;
int n, target, minEdges = INF;
int size[MAXN], dist[MAXN], depth[MAXN], centroid, minSubtreeSize;
int tempDist[MAXN], tempDepth[MAXN], tempCount;
int distanceCount[MAXN];
bool visited[MAXN];
void addEdge(int u, int v, int w) {
edges[++edgeCount] = {v, w, head[u]};
head[u] = edgeCount;
}
void findCentroid(int u, int parent, int totalNodes) {
size[u] = 1;
int maxSubtree = 0;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == parent || visited[v]) continue;
findCentroid(v, u, totalNodes);
size[u] += size[v];
maxSubtree = max(maxSubtree, size[v]);
}
maxSubtree = max(maxSubtree, totalNodes - size[u]);
if (maxSubtree < minSubtreeSize) {
minSubtreeSize = maxSubtree;
centroid = u;
}
}
void gatherPathData(int u, int parent, int d, int depthCount) {
tempDist[++tempCount] = d;
tempDepth[tempCount] = depthCount;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (v == parent || visited[v]) continue;
gatherPathData(v, u, d + edges[i].weight, depthCount + 1);
}
}
void processSubtree(int u, int parent, int totalNodes) {
minSubtreeSize = totalNodes - 1;
centroid = u;
findCentroid(u, parent, totalNodes);
visited[centroid] = true;
for (int i = head[centroid]; i; i = edges[i].next) {
int child = edges[i].to;
if (child == parent || visited[child]) continue;
tempCount = 0;
gatherPathData(child, centroid, edges[i].weight, 1);
int subtreeStart = tempCount - size[child] + 1;
for (int j = subtreeStart; j <= tempCount; ++j) {
if (tempDist[j] <= target) {
minEdges = min(minEdges, tempDepth[j] + distanceCount[target - tempDist[j]]);
}
}
for (int j = subtreeStart; j <= tempCount; ++j) {
if (tempDist[j] <= target) {
distanceCount[tempDist[j]] = min(distanceCount[tempDist[j]], tempDepth[j]);
}
}
}
for (int i = 1; i <= tempCount; ++i) {
if (tempDist[i] <= target) {
distanceCount[tempDist[i]] = INF;
}
}
for (int i = head[centroid]; i; i = edges[i].next) {
int child = edges[i].to;
if (child == parent || visited[child]) continue;
processSubtree(child, centroid, size[child]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> target;
fill(distanceCount, distanceCount + MAXN, INF);
distanceCount[0] = 0;
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u + 1, v + 1, w);
addEdge(v + 1, u + 1, w);
}
processSubtree(1, 0, n);
if (minEdges != INF) cout << minEdges;
else cout << -1;
return 0;
}