Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of all edge pairs. Thus, there are total nC2 or n(n-1)/2 such pairs. The time complexity of the mentioned algorithm is n(n-1)/2. Please suggest an algorithm with better space and time complexity if possible. Below is the java implementation.

    import java.util.*;
    
    public class AllPairSumTree {
    	
    	static long sumAllPairs = 0;
    	
    	public static void main(String[] args) {
    		/*
    		 * Total Number of vertices
    		 */
    		int N = 7;
    		/*
    		 * Adjacency List
    		 */
    		LinkedList<Integer>[] adjacencyList = new LinkedList[N];
    		/*
    		 * Initialize Adjacency List
    		 */
    		for(int ii=0; ii<N;ii++) {
    			adjacencyList[ii] = new LinkedList<Integer>();
    		}
    		/*
    		 * Weighted Graph Matrix
    		 */
    		int[][] weightedGraph = new int[N][N];
    		/*
    		 * Initialize Matrix
    		 */
    		for(int ii=0;ii<N;ii++) {
    			for(int jj=0;jj<N;jj++) {
    				if(ii == jj) {
    					weightedGraph[ii][jj] = 0;
    				}else {
    					weightedGraph[ii][jj] = Integer.MAX_VALUE;
    				}
    			}
    		}
    
    		/*
    		 * Input Pattern: vertex1,  vertex2, cost
    		 * 
    		 * Total Vertex: N, Total Edges: N-1 (Tree, Undirected Graph)
    		 */
    		int[] inputGraph = { 1, 2, 1,
    								2, 3, 2,
    								3, 4, 3,
    								3, 5, 4,
    								5, 6, 6,
    								5, 7, 5};
    		
    		/*
    		 * Assign  Adjacency List  and Matrix with input Graph
    		 */
    		for(int ii=0; ii<N-1; ii++) {
    			int vertex1 = inputGraph[ii*3 + 0] - 1;
    			int vertex2 = inputGraph[ii*3 + 1] - 1;
    			int cost = inputGraph[ii*3 + 2];
    			
    			adjacencyList[vertex1].add(vertex2);
    			adjacencyList[vertex2].add(vertex1);	//bidirectional edge
    			
    			weightedGraph[vertex1][vertex2] = cost;
    			weightedGraph[vertex2][vertex1] = cost; //bidirectional edge
    		}
    
    		sumAllPairs = 0;
    		int currentVertex = 0;
    		LinkedHashSet<Integer> visitedSet = new LinkedHashSet<Integer>(N);
    		int lastVisitedVertex = -1;
    		allPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex);
    
    		System.out.println(sumAllPairs);
    	}
    	
    	/*
    	 * Say graph has vertices 1,2,3,4,5,6,7
    	 * 
    	 * allPairSum() will compute sum of edges like this:
    	 * 				21 + (31+32) + (41+42+43) + (51+52+53+54) + (61+62+63+64+65)+(71+72+73+74+75+76)
    	 * 				where ij represents edge from vertex i to vertex j
    	 * 
    	 * Time Complexity:
    	 * 		N(N-1)/2 or Combination(N,2)[![enter image description here][1]][1]
    	 */
    	private static void allPairSum(int[][] weightedGraph, LinkedList<Integer>[] adjacencyList, int currentVertex, LinkedHashSet<Integer> visitedSet, int lastVisitedVertex) {
    
    		for(Integer visitedVer : visitedSet) {
    			int cost = weightedGraph[visitedVer][lastVisitedVertex] +  weightedGraph[lastVisitedVertex][currentVertex];
    			sumAllPairs += cost;
    			weightedGraph[visitedVer][currentVertex] = cost;
    			weightedGraph[currentVertex][visitedVer] = cost;
    		}
    
    		visitedSet.add(currentVertex);
    
    		for(Integer neighbourVert : adjacencyList[currentVertex]) {
    			if(neighbourVert != lastVisitedVertex) {
    				/*
    				 * 		neighbourVert becomes currentVertex
    				 * 		currentVertex becomes lastVisitedVertex
    				 */
    				allPairSum(weightedGraph, adjacencyList, neighbourVert, visitedSet, currentVertex);
    			}
    		}
    	}
    }


    


  [1]: https://i.sstatic.net/QfiXx.jpg