title: Sum of all shortest paths queries
body: <p>I need help with this problem.</p>
  
  <p>We have that <code>D(G,u,v)</code> is number of edges on shortest path from <code>u</code> to <code>v</code> in graph <code>G</code>.</p>
  
  <p>We are given a tree <code>T</code> with <code>N</code> vertices and <code>Q</code> queries of following type:</p>
  
  <p>If we add edge <code>(a,b)</code> to tree <code>T</code>, obtaining graph <code>G1</code>, then what is the value of <code>sum(1 &lt;=u &lt; v &lt;= N) D(G1,u,v)</code></p>
  
  <p>Queries are independent</p>
  
  <pre><code>1&lt;=N&lt;=260000
  
  1&lt;=Q&lt;=200000
  
  D(T,a,b)&lt;=16
  </code></pre>
  
  <p>For each query I called BFS from every node and calculated sum of distances, but my algorithm was to slow. Can someone give me more efficient approach?</p>