Funcia
Lv.4centroid-decompositiondivide-and-conquertreetwo-pointers

Village Pairs Within Distance K

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

nedgeskresult
5[[0, 1, 2], [1, 2, 3], [1, 3, 1], [3, 4, 4]]46
3[[0, 1, 5], [1, 2, 5]]40
4[[0, 1, 1], [0, 2, 1], [0, 3, 1]]26

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

  • 1≤1 \le n ≤50,000\le 50{,}000
  • edges.length == n −1- 1, edges[i] = [u, v, w], 0≤u,v<0 \le u, v < n, 1≤w≤10,0001 \le w \le 10{,}000
  • The roads form a tree.
  • 0≤0 \le k ≤109\le 10^9
  • The answer may not fit in 32 bits.

Expected complexity

Time
O(N log^2 N)
Space
O(N)

Examples

nedgeskExpected
5[[0,1,2],[1,2,3],[1,3,1],[3,4,4]]46
3[[0,1,5],[1,2,5]]40
4[[0,1,1],[0,2,1],[0,3,1]]26

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 O(log⁡n)O(\log n)). To count pairs through c, sort the distances from c (including c itself at 0) and count pairs with sum ≤k\le k by two pointers, then subtract the pairs counted the same way inside each piece, since those do not really pass through c. Total O(nlog⁡2n)O(n \log^2 n); a DFS from every vertex is O(n2)O(n^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)226 msestimated
C++ (GCC, gnu++23)226 msderived
Python 3.131966 msderived
Java 252196 msderived
Kotlin 2.4 (JVM)1452 msestimated
C# 14 (.NET 10)1452 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance605verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.