9

Question:

Given an undirected graph of N nodes and N-1 edges. The length of all edges are 1. Each edge i has a weight of Wi. (0 <= Wi <= 10.000)

The graph is guaranteed to not have any loops. So there's always one (and only) shortest path between 2 nodes.

Take a pair of node (u, v) from the graph:

  • l is the length of shortest the path between the 2 nodes
  • w is the edge with the largest weight in the shortest path between the 2 nodes

Given the number K, count the number of pair (u, v) from the graph such that w - l >= K

Example:

N = 3, K = 1
Edges:
1 - 2 - 3
1 - 3 - 2

(Edges are described as: u - v - w)

Answer: 6. All the possible pairs are: (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)

Brute Force Solution (N < 100):

Go over all pairs of (u, v), find the shortest path along side with w and l. Increase the answer if w - l >= K.

Time complexity: O(N^3)

P/S: I have tried and succeeded the brute force solution (with N < 100). But I'm struggling to find a solution with N up to 100.000

Olivier
  • 13,283
  • 1
  • 8
  • 24
unglinh279
  • 675
  • 4
  • 24
  • 2
    What does "maximum weight in the shortest path between the 2 nodes" mean? Is it the edge with the highest weight in the path or is it the total path cost, comparing different shortest paths between the two nodes? What if two shortest paths between `u` and `v` have different maximum single-edge weight? Is there an assumption that only one shortest path exists from u to v? – גלעד ברקן Sep 30 '21 at 15:35
  • 1
    @גלעדברקן "maximum weight in the shortest path between the 2 nodes" is the edge with the highest weight in the path. There is only 1 shortest path for every pair of (u, v) nodes. – unglinh279 Sep 30 '21 at 16:27
  • Is this online somewhere for testing? – no comment Sep 30 '21 at 16:55
  • @don'ttalkjustcode no, sorry. It's an old problem from my school last year – unglinh279 Sep 30 '21 at 17:20
  • Do you have some testing code yourself, or how do you test? Is there a time limit or other information not included in your question? What's your "brute force solution" and its complexity? – no comment Sep 30 '21 at 17:52
  • @don'ttalkjustcode there's only 2 limits, one with N < 100 and one with N < 100.000. i've added the "brute force solution" description above. – unglinh279 Oct 01 '21 at 00:18
  • 3
    Hint: Centroid decomposition should work with time complexity around O(n log²(n)) – user202729 Oct 01 '21 at 05:39
  • 1
    Your graph is a tree (loop free, n nodes, n-1 edges), so there's only one path between any pair of nodes. – Dave Oct 09 '21 at 02:29
  • @unglinh279 The usual graph-theory definition: distinct nodes – Dave Oct 09 '21 at 03:13

1 Answers1

7

To work out user202729's hint:

  1. Find the centroid (vertex whose removal leaves subtrees that each have at most half of the vertices of the whole tree).

  2. Count the pairs (u, v) whose path contains the centroid.

  3. Delete the centroid and operate recursively on each of the subtrees.

Step 1 is O(n) (there's a standard algorithm) and Step 2 will be O(n log n), so the Master Theorem gives O(n log2 n) for the whole.

To implement Step 2, root the tree at the centroid and calculate, for the centroid and each of its children, the number of descendants at each depth. Put the results in Fenwick trees for O(log n)-time prefix sums.

Now, sort the edges by weight. Starting with the heaviest edge e and working our way to the lightest, we count the pairs whose path has e as its heaviest edge. The edge e connects a parent and a child; let x be the child. For each (improper, so including x) descendant u of x, let ℓ* = w − K be the greatest ℓ such that w − ℓ ≥ K. With two prefix sums, count the number of vertices v in other subtrees at depth at most ℓ* − depth(u). Then issue updates to the Fenwick trees to remove u from the count.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • I don't really understand the usage of the Fenwick Tree, what is store in it? And can you please explain the last step more clearly? – unglinh279 Oct 05 '21 at 17:34
  • 2
    @unglinh279 we need to store (e.g.) there's 10 vertices at distance 1 from the root, 30 at distance 2, and 25 at distance 3 and be able to quickly answer queries like "how many vertices at distance ≤2?" and decrease the counts after we process a vertex. – David Eisenstat Oct 05 '21 at 17:38
  • If you have time, can you please provide a pseudo code? I understand the centroid and Fenwick Trees part but can't work out how you can count the number of vertices for each edges. – – unglinh279 Oct 06 '21 at 14:45
  • The part with the edges, does that happen *after* steps 1 to 3 have been done to the whole tree? Or is it part of every step 2? – no comment Oct 09 '21 at 07:07
  • @don't talk just code it's part of step 2. We could save time in practice by doing the sort once and selecting, but the Fenwick trees will keep the asymptotic running time the same. – David Eisenstat Oct 09 '21 at 12:50
  • The last paragraph sounds like nested loops `for each edge e: for each descendant u: ...`. Isn't that quadratic? – no comment Oct 10 '21 at 00:11
  • @don't oh, it was implied that those get deleted before we consider the next edge. – David Eisenstat Oct 10 '21 at 01:31
  • Ok I think I got it now. And with "two prefix sums", you mean the root's prefix sum minus the prefix sum of the child whose subtree the edge is in, right? And one other thing: Am I right in thinking that we *could* build the Fenwick trees in linear time with BFS, but that it's pointless because the removals will make it linearithmic anyway? – no comment Oct 11 '21 at 22:50
  • @don'ttalkjustcode Yes. – David Eisenstat Oct 11 '21 at 23:11