Sum of all paths between all pairs of nodes in a tree
\$O(n^2)\$ time complexity

Your current algorithm has \$O(n^2)\$ time complexity because for each edge, you count the number of vertices on one side of the edge, which is a linear time operation.

However, the program is pretty fast.  I ran it on three large test cases.  The first was 10000 nodes arranged in a line, the second was 10000 nodes arranged in a star, and the third was 10000 nodes arranged in a star, but with the edges listed with reverse direction.  Here were the results:

Line : 1.15 sec
Star : 0.01 sec
Star2: 2.30 sec


The first star was quick because the program always counted the outside (i.e. 1 node always).  The second star was slow because the program always counted the inside (n-1 nodes always).  So you could consider these the best and worst possible test cases.

Alternative strategy

The problem can be solved in \$O(n)\$ time.  Instead of picking a random edge and having to count one side, if you picked an edge connected to a leaf node, you automatically know that the count on the leaf side is 1.  There is always at least 1 leaf node in the graph, because the graph is a spanning tree with no cycles.  If you then remove the leaf node from the graph, there must still be at least 1 leaf node, so you can keep finding a leaf node and removing it until there are no nodes left.

A small complication arises after you find the first leaf node and remove it from the tree.  The node it was attached to must now remember that it was connected to the leaf, in order to keep the distance calculations correct.  In other words, if leaf A is attached to node B and leaf A is removed, then node B must now count as 2 nodes.  If node B is later removed, it must add its 2 nodes to some other node, etc.

So the pseudocode is this:


Find a node with 1 edge only.  Call this node A and the node it is attached to B.
Add to the total distance this amount: A.count * (totalNodes - A.count) * edge.weight.
Add A.count to B.count.
Remove the edge from A and B.
Go back to step 1.  If B only has 1 edge, use B as the next node.


You can find all the leaf nodes in \$O(n)\$ time because:


In the beginning there are a fixed number of leaf nodes.
If you scan the nodes array from beginning to end, you will find these initial leaf nodes in \$O(n)\$ time.
Any other nodes that become leaf nodes are found in step 5 above and can be handled without scanning.


Similarly, finding and removing edges can be done in amortized \$O(n)\$ time if you handle the edge lists correctly.  One key point is that even though you need to search through edge lists, there are only \$n\$ total edges, so that total time spent searching through edge lists is limited to \$O(n)\$.

Sample \$O(n)\$ program

Here is the program I wrote in C with the alternative strategy.  It solved all three test cases in 0.01 seconds.

Note: I did edge removal in a somewhat nonstandard way, where I marked the edge invalid instead of removing it from the edge list.  I wrote another version where I kept the edges in a doubly linked circular list and I actually removed the edge from the list when needed.  Both versions are just as fast, so if anyone wants to see the other version, just ask.

#include &lt;stdio.h&gt;
#include &lt;stdint.h&gt;
#include &lt;stdlib.h&gt;

const int MOD = 1300031;

typedef struct Edge {
    struct Edge *next;
    int          to;
    int          weight;
} Edge;

typedef struct Node {
    int         numConnected;
    int         numEdges;
    Edge       *edges;
} Node;

int main(void)
{
    int   numTests = 0;
    Node *nodes    = NULL;
    Edge *edges    = NULL;

    scanf("%d", &amp;numTests);
    for (int i=0; i&lt;numTests; i++) {
        int numNodes = 0;
        int e        = 0;

        scanf("%d", &amp;numNodes);
        nodes = (Node *) calloc(numNodes, sizeof(*nodes));
        edges = (Edge *) calloc(2*numNodes, sizeof(*edges));

        // Read in list of edges.  For each edge, we create two Edge
        // structures and add one to each endpoint Node.
        for (int j = numNodes - 1; j &gt; 0; j--) {
            int from   = 0;
            int to     = 0;
            int weight = 0;
            scanf("%d %d %d", &amp;from, &amp;to, &amp;weight);
            from--;
            to--;

            edges[e].to       = to;
            edges[e].next     = nodes[from].edges;
            edges[e].weight   = weight;
            nodes[from].edges = &amp;edges[e];
            nodes[from].numEdges++;
            e++;

            edges[e].to       = from;
            edges[e].next     = nodes[to].edges;
            edges[e].weight   = weight;
            nodes[to].edges   = &amp;edges[e];
            nodes[to].numEdges++;
            e++;
        }

        int      search = 0;
        int      cur    = -1;
        uint64_t dist   = 0;

        for (int nodesLeft = numNodes-1; nodesLeft &gt; 0; nodesLeft--) {
            Edge *edge;

            // Either use the node known to have 1 edge, or find the next
            // node that has 1 edge.
            if (cur == -1) {
                while (nodes[search].numEdges != 1) {
                    search++;
                    if (search &gt;= numNodes) {
                        printf("ERROR, reached end of nodes\n");
                        exit(1);
                    }
                }
                cur = search++;
            }

            // Find the one valid edge in the list of edges.
            for (edge = nodes[cur].edges; edge != NULL; edge = edge-&gt;next) {
                if (edge-&gt;to != -1)
                    break;
            }
            if (edge == NULL) {
                printf("ERROR, reached end of edges\n");
                exit(1);
            }

            // The edge is going from cur &lt;-&gt; to, where cur is a leaf node.
            // We can calculate the distance used by the edge because we know
            // how many nodes are attached to cur.  That number is 1 for cur
            // itself plus nodes[cur].numConnected which is the number of
            // previous leaf nodes that we removed that are connected to cur.
            int to       = edge-&gt;to;
            int curNodes = nodes[cur].numConnected + 1;

            dist += (numNodes - curNodes) * curNodes * edge-&gt;weight;

            // Since we are removing the leaf node cur, we add its nodes
            // to the node it is attached to.
            nodes[to].numConnected += curNodes;

            // If the new node has 1 edge, use it, otherwise set cur to
            // negative to search for another node with 1 edge.
            if (--nodes[to].numEdges == 1)
                cur = to;
            else
                cur = -1;
            nodes[cur].numEdges = 0;

            // Delete other side of edge by marking its to field as -1.
            // This is needed so that when we search through the other
            // node's edges for its one remaining edge, we will skip this one.
            // We can find the paired edge by looking at its array index
            // because always created edges in consecutive pairs.
            int edgePairIndex = (edge - &amp;edges[0]) ^ 0x1;
            edges[edgePairIndex].to = -1;
        }

        // printf("%lld\n", dist);
        printf("%lld\n", dist % MOD);
        free(edges);
        free(nodes);
    }
}