title: Sum of maximum flow between every pair of vertices of a tree
body: <p>Given a undirected tree with <code>N</code> vertices numbered from 1 to N. Each edge tree has some capacity. Find the sum of maximum flow between all possible pair of vertices. There exist only one way to go between any two vertices.<br/>
  Find the sum of maximum flow between all possible pair of vertices. </p>
  
  <p>For eg: In given tree with 3 edges <br/>
  <code>1 2 5</code> <br/>
  <code>2 3 6</code> <br/>
  Edges between node 1 and node 2 with capacity 5, node 2 and node 3 with capacity 6. <br/>
  <code>Output - 32</code> <br/></p>
  
  <p><code>(1,2) = (2,1) = 5</code> <br/>
  <code>(1,3) = (3,1) = 5</code> <br/>
  <code>(2,3) = (3,2) = 6</code> <br/>
  Therefore output is <code>(5+5+6)*2 = 32</code><br/></p>
  
  <p>My Approach- <br/></p>
  
  <ol>
  <li><code>Sort</code> edges based on edge_capacity</li>
  <li><p>While <code>edge_list</code> is <code>not empty</code>: remove edge with minimum capacity</p>
  
  <ul>
  <li>count number of nodes on <code>left</code> and <code>right</code> of this edge. Do DFS for node count</li>
  <li>Add (<code>left_count</code> * <code>right_count</code> * <code>edge_capacity</code>) to the answer.</li>
  </ul></li>
  <li><p>return <code>answer*2</code>. <br/></p></li>
  </ol>
  
  <p>Time complexity is O(n<sup>2</sup>). This solution gives TLE.<br/> 
  How can we further reduce the time complexity? <br/><br/>
  My code- </p>
  
  <pre><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)
  
  for _ in range(int(raw_input())):   # Iterate for multiple test cases
      MOD = 1000000007
      edges = []
      n = int(raw_input())            # number of vertices
      nodes = [set() for _ in range(n)]
      for __ in range(n-1):           # read input for 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
      for i 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
  </code></pre>
  
  <p>Link to the original problem-
  <a href="http://www.spoj.com/problems/PRJAN15E/" rel="nofollow">Spoj-Flow on Tree</a>  <br/></p>
  
  <p><br/>
  <strong>Updates</strong></p>
  
  <p>Constraints-</p>
  
  <ol>
  <li>Number of test cases - 10</li>
  <li>1 &lt;= N &lt;= 10<sup>5</sup>  (number of vertices in each test case)</li>
  <li>Capacities of each edge will be non-negative and no more than 10<sup>6</sup>.</li>
  <li>The total number of vertices among all test cases will be less than 5*10<sup>5</sup>.</li>
  </ol>