Count Tree Paths With Limited Max Edge Weight
Problem Overview
A path between two nodes of a tree is unique, and the heaviest edge on that path is the threshold that decides whether the path is allowed for a query x.
Intuition
A path between two nodes of a tree is unique, and the heaviest edge on that path is the threshold that decides whether the path is allowed for a query x. Keeping only edges of weight at most x breaks the tree into connected components. Every pair of nodes inside the same component has a path whose heaviest edge is at most x, and every such pair is counted once. Sorting the edges by weight and merging them with a disjoint set grows those components in increasing threshold order. When components of sizes a and b join across an edge of weight w, every node of the first component forms a new valid path with every node of the second, so a times b paths are added and their heaviest edge is exactly w. Queries are sorted the same way. As edges are added, each query reads the running path count when every edge of weight at most its limit has been merged. The original order of the queries is restored by writing into the matching index. The product of the two sizes is formed in a 64 bit integer so a large merge does not wrap before it is stored.
Algorithm
- 1Start each node in its own component of size 1, and sort the edges by weight.
- 2Pack each query with its original index and sort those packs by the query limit.
- 3Walk the sorted queries. While the next edge weight is at most the current limit, merge its endpoints.
- 4When two different components merge, add the product of their sizes to the running path count and attach the smaller root under the larger one.
- 5Store the running path count at the original index of the query, then return the list.
Example Walkthrough
Input: n = 7, edges = [[1, 2, 3], [2, 3, 1], [2, 4, 9], [3, 6, 7], [3, 5, 8], [5, 7, 4]], queries = [1, 3, 5]
- 1. For limit 1 the edge of weight 1 joins nodes 2 and 3, so one path is counted.
- 2. For limit 3 the edge of weight 3 joins node 1 with that component of size 2, adding two paths. The total becomes 3.
- 3. For limit 5 the edge of weight 4 joins nodes 5 and 7, adding one more path. The total becomes 4.
Output: [1, 3, 4]
Common Pitfalls
- • A path needs at least one edge. A lone node does not contribute a path.
- • Merge only when the roots differ. An edge inside an existing component adds no new path.
- • Multiply the component sizes as a 64 bit product before adding them to the running count.
- • Answer queries offline in sorted order, then write each count back to its original index.
// Approach: A path whose heaviest edge is at most x uses only edges of
// weight at most x. Sorting the edges by weight and merging them with a
// disjoint set grows the connected components in that order. When two
// components of sizes a and b join, a * b new paths appear. Queries are
// sorted the same way and answered offline as edges are added.
// Complexity: O((n + q) log n) time, O(n + q) extra space.
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public ArrayList<Integer> maximumWeight(int n, int[][] edges, int[] queries) {
int[] parent = new int[n + 1];
int[] size = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
int q = queries.length;
long[] order = new long[q];
for (int i = 0; i < q; i++)
order[i] = ((long) queries[i] << 32) | i;
Arrays.sort(order);
ArrayList<Integer> res = new ArrayList<>(q);
for (int i = 0; i < q; i++)
res.add(0);
long paths = 0;
int edgeIdx = 0;
int edgeCount = edges.length;
for (int i = 0; i < q; i++) {
int limit = (int) (order[i] >>> 32);
int idx = (int) order[i];
while (edgeIdx < edgeCount && edges[edgeIdx][2] <= limit) {
int u = find(parent, edges[edgeIdx][0]);
int v = find(parent, edges[edgeIdx][1]);
if (u != v) {
if (size[u] < size[v]) {
int temp = u;
u = v;
v = temp;
}
paths += (long) size[u] * size[v];
parent[v] = u;
size[u] += size[v];
}
edgeIdx++;
}
res.set(idx, (int) paths);
}
return res;
}
private static int find(int[] parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}