In this editorial we assume that the weights of the edges are pairwise distinct. Although there are no such conditions in the constraints, but tie-breaks can be done by, for example, comparing their indices.

For each \(i \, (1 \leq i \leq N -1)\), we will count the total number of pairs \((u, v)\) such that \(f(u, v) = w_i\). \(f(u, v) = w_i\) holds if and only if the path connecting Vertices \(u\) and \(v\) contains Edge \(i\) and any other edge in the path has a smaller weight than \(w_i\).

A graph that only contains the edges with weights less than \(w_i\) forms a forest (in terms of graph theory), and \(u_i\) and \(v_i\) always belong to different connected components. \(f(u, v) = w_i\) holds if and only if \(u\) belongs to one of these connected component and \(v\) to the other.

Therefore, the problem can be solved by adding the edges to the graph in the increasing order of weights and obtaining the size of the connected components with data structures like Union-Find.

Sample code (C++)