Giving an undirected weighted graph of n (n <= 1e5) vertices , n — 1 edges and an positive integer k (k <= 1e9). Count the number of pairs (i , j) that i < j and the weight of the path from i to j is not bigger than k.
Input the first line contain n and k the following n — 1 lines each contains three positive integer u , v , w (u , v <= n , w <= 1e9)
Output the number of pairs (i , j) that the weight of the path from i to j is not bigger than k.
Sample
INPUT
6 8
1 2 2
2 3 4
2 5 1
4 5 3
5 6 5
OUTPUT
14
Centroid decomposition or DSU on tree
Can you explain more about it
What do you mean saying DSU on tree? I didn't hear about this technique yet. Please, provide more info.
Oh, it is here: DSU on tree
Oh wow, if using the centroid decomposition, how to avoid trying every pair(i,j).
Consider centroid c. We calculate all distances from c to remaing vertices. If distance to vertex
visd, we need to count the number of verticesuwith distance tocless or equal tok - d, and pathu--vcomes throughc. We can shrink coordinates and build a segment tree, and the number of such vecticesuwill be a sum on prefix. If we don't like shrinking coordinates, we can simply use treap instead of segtree, but it can get TLE.So basically for centroid c (after centroid decomp) we can precalculate the distances and compress the coords then build a segment tree on it so we can query it quickly? Btw prob a Dynamic ST works?
Yes, Dynamic ST works, but it requires
O(n log n log C)memory. It probaly gets MLE. But you can replace it by classical ST with compressed coordinates.Let
dbe a distance fromcto some vertexv. Notice that all coordinates you use in ST can be written asdork - d. So you need only these values in ST.How can you use DSU on tree on arbitrary graph? We can use centroid decomposition on arbitrary graph as explained here, but what about DSU on tree?