-1

I have a tree with N nodes and each edge has some weight. I have to find, for all pairs (u,v) 1<=u<=N 1<=V<=N, the maximum weight in the path from U to V. How can I find the total sum of the maximum weight for every pair (U,V)?

Jonny Henly
  • 4,023
  • 4
  • 26
  • 43
Sunny
  • 381
  • 4
  • 13
  • Do you mean like the following Stack Overflow question: [How to find maximum spanning tree?](http://stackoverflow.com/questions/4992664/how-to-find-maximum-spanning-tree) – Jonny Henly Apr 18 '16 at 07:32

3 Answers3

0

You can use Floyd Warshall Algorithm. You can multiply each edges with (-1), and solve your problem like finding the shortest path between all pairs, then multiply your result with (-1).

Priyansh Goel
  • 2,660
  • 1
  • 13
  • 37
0

For every node, you can extend it to a tree. The extend process of node x is, for every edge (x, y), if value[x] > value[y] then we go to node y and continue the process, so the result of extending node x is a tree, and the value of x is the largest of all.

There are possibility that some value of the tree are equal maximum, to break the tie, we can assign each node an index, to make the value like a pair (value[x], idx[x]), and each idx is different.

Then for each extended tree, suppose the node with max value is x, take it as the root, suppose it has m subtree, each has total node number num[i], then every path between two node from different subtree has max weight value[x], so value[x] counts SUM[num[i]*num[j]] (i != j) times, ie. (SUM[num[i]]^2-SUM[num[i]^2])/2, and we miss the path starting from node x, so we should also count SUM[num[i]] more times. num can be generated during the extending process.

This is a O(n^2) solution. And I believe there is other much more faster algorithm.

delta
  • 3,778
  • 15
  • 22
0

Given a tree T, let S(T) be the sum you're interested in: the sum over every pair of vertices of the largest weight of an edge in the path between them.

If T has no edges then it has 1 vertex, and S(T) = 0.

Otherwise, consider the largest edge E in the tree, and say its weight is W. If you remove this edge from the tree, you end up with two smaller trees (call them T1 and T2). Let's say T1 is the tree above the edge (that is, the subtree that contains the root of T).

If u is in T1 and v is in T2, then the largest edge in any path between them goes through E, which has weight W and is guaranteed to be the largest weight in the path. Otherwise, if u and v are both in T1, then the path between them stays inside T1. Same for T2.

Thus S(T) = 2*W*v(T1)*v(T2) + S(T1) + S(T2). (where v(T) means the number of vertices of T).

This gives you a recursive formula for computing S(T), and the only difficulty is finding the largest edge quickly in the subproblems.

One way is to store in each vertex of the tree the maximum weight of any edge below that vertex. Then you can find the largest weight in the whole tree in O(log(v(T)) time, and when you, following the algorithm above, remove that largest weight, you can patch up the weights in the part of the tree above the edge in log(v(T1)) time. The weights in T2 don't need adjusting.

Overall, this gives you an O(v(T)log(v(T))) algorithm. Each edge is removed exactly once, and there's at most O(log(v(T))) work per step.

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118