Village Pairs Within Distance K
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
n villages (0..n-1) are connected by n-1 two-way roads so that every pair has exactly one path (a tree);
edges[i] = [u, v, w] is a road of length w. The distance between two villages is the total length of the path between
them. Return the number of unordered pairs {a, b} (a ≠ b) whose distance is at most k.
Examples
| n | edges | k | result |
|---|---|---|---|
5 | [[0, 1, 2], [1, 2, 3], [1, 3, 1], [3, 4, 4]] | 4 | 6 |
3 | [[0, 1, 5], [1, 2, 5]] | 4 | 0 |
4 | [[0, 1, 1], [0, 2, 1], [0, 3, 1]] | 2 | 6 |
Example 1 — {0,1}, {0,3}, {1,2}, {1,3}, {2,3}, {3,4} are within 4; {0,2} and {1,4} are 5 apart.
Example 2 — even the closest pair is 5 apart.
Example 3 — in the star every pair is within 2.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(n: int, edges: int[][], k: int) → long
Constraints
-
n edges.lengthn,edges[i] = [u, v, w],n,- The roads form a tree.
-
k - The answer may not fit in 32 bits.
Expected complexity
- Time
- O(N log^2 N)
- Space
- O(N)
Examples
| n | edges | k | Expected |
|---|---|---|---|
5 | [[0,1,2],[1,2,3],[1,3,1],[3,4,4]] | 4 | 6 |
3 | [[0,1,5],[1,2,5]] | 4 | 0 |
4 | [[0,1,1],[0,2,1],[0,3,1]] | 2 | 6 |
Hint
Hint
Use centroid decomposition. For a centroid c, every path either passes through c or lies entirely inside one of the
pieces left after removing c (handled recursively; pieces are at most half the size, so the depth is ). To count
pairs through c, sort the distances from c (including c itself at 0) and count pairs with sum by two pointers,
then subtract the pairs counted the same way inside each piece, since those do not really pass through c. Total
; a DFS from every vertex is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 226 ms | estimated |
| C++ (GCC, gnu++23) | 226 ms | derived |
| Python 3.13 | 1966 ms | derived |
| Java 25 | 2196 ms | derived |
| Kotlin 2.4 (JVM) | 1452 ms | estimated |
| C# 14 (.NET 10) | 1452 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 5 | verdict only |