User0069's blog

A very very hard problem (need help)
By User0069, history, 17 months ago, In English

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
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
17 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Centroid decomposition or DSU on tree

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain more about it

    → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    What do you mean saying DSU on tree? I didn't hear about this technique yet. Please, provide more info.

    → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh wow, if using the centroid decomposition, how to avoid trying every pair(i,j).

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Consider centroid c. We calculate all distances from c to remaing vertices. If distance to vertex v is d, we need to count the number of vertices u with distance to c less or equal to k - d, and path u--v comes through c. We can shrink coordinates and build a segment tree, and the number of such vectices u will 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.

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 d be a distance from c to some vertex v. Notice that all coordinates you use in ST can be written as d or k - d. So you need only these values in ST.

          → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply