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);
            }
        }
    }
}