algorithm - Sum of maximum flow between every pair of vertices of a tree -

given undirected tree n vertices numbered 1 n. each edge tree has capacity. find sum of maximum flow between possible pair of vertices. there exist 1 way go between 2 vertices.
find sum of maximum flow between possible pair of vertices.

for eg: in given tree 3 edges
1 2 5
2 3 6
edges between node 1 , node 2 capacity 5, node 2 , node 3 capacity 6.
output - 32

(1,2) = (2,1) = 5
(1,3) = (3,1) = 5
(2,3) = (3,2) = 6
therefore output (5+5+6)*2 = 32

my approach-

1. sort edges based on edge_capacity

2. while edge_list not empty: remove edge minimum capacity

   • count number of nodes on left , right of edge. dfs node count
   • add (left_count * right_count * edge_capacity) answer.

3. return answer*2.
   

time complexity o(n²). solution gives tle.
how can further reduce time complexity?

code-

def dfs(node):     count = 1     visited = set()     stack = [node]     while stack:         vertex = stack.pop()         if vertex not in visited:             visited.add(vertex)             stack.extend(set(nodes[vertex]) - visited)     return len(visited)  _ in range(int(raw_input())):   # iterate multiple test cases     mod = 1000000007     edges = []     n = int(raw_input())            # number of vertices     nodes = [set() _ in range(n)]     __ in range(n-1):           # read input number of edges         edges.append(map(int, raw_input().split()))         nodes[edges[-1][0]-1].add(edges[-1][1]-1)             nodes[edges[-1][1]-1].add(edges[-1][0]-1)         edges[-1][0]-=1; edges[-1][1]-=1;      edges.sort(key=lambda x: x[2])      answer = 0     in range(len(edges)):         weight = edges[i][2]         x, y = edges[i][0], edges[i][1]         nodes[x].remove(y)         nodes[y].remove(x)         left_count = dfs(x)         right_count = dfs(y)         answer += ((left_count*right_count*weight)%mod)     print (answer*2)%mod 

link original problem- spoj-flow on tree

updates

constraints-

1. number of test cases - 10
2. 1 <= n <= 10⁵ (number of vertices in each test case)
3. capacities of each edge non-negative , no more 10⁶.
4. the total number of vertices among test cases less 5*10⁵.

make sure aware of following 2 things:

• we can find "all pairs shortest path" in tree in linear time, using dynamic programming.

• max flow on path min of edge weights, rather sum.

once that's done, can use dynamic programming again add flows in linear time.