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