Let us consider how to compute \(f(i,j)\) quickly.

First, we represent the structure of \(G\) using a rooted binary tree \(U\) that represents the process of union-find. Specifically, \(U\) has exactly \(N\) leaves and \(N-1\) internal vertices. Each leaf corresponds to a vertex of \(G\). Each internal vertex \(k\) has a weight \(w_k\) assigned to it. If the LCA of leaves \(i,j\) is internal vertex \(k\), then the capacity of the edge connecting \(i,j\) in \(G\) is \(w_k\).

Let us consider the structure of the minimum cut separating \(i,j\) on \(G\). In fact, the following property holds.

• Cutting an edge \(e\) of \(U\) yields two trees. Let \(X_e\) be the set of leaves contained in the tree not containing the root, and let \(Y_e\) be the set of leaves contained in the tree containing the root. Then, there exists some \(e\) such that \(X_e\) and \(Y_e\) give the minimum cut between \(i,j\).

If we assume this property, the problem is easily solved. For each edge \(e\) of \(U\), compute the cost of the corresponding cut and set it as the weight of that edge. Then, \(f(i,j)\) is the minimum weight of the edges on the path between leaves \(i,j\) in \(U\). Aggregating this value over all pairs can be done using union-find. The time complexity is \(O(N \log N)\).

Sample Solution (C++)

Finally, let us prove the property stated above.

Let \((I,J)\) be an \(i,j\) cut on \(G\). We have \(i \in I, j \in J\). Let \(k\) be the LCA of leaves \(i,j\). Among the children of \(k\), let \(X\) be the ones containing \(i\), and \(Y\) be the ones containing \(j\). Let \(Z\) be the vertices outside the subtree of \(k\). Let \(X_I\) be the leaves within \(X\) that are contained in \(I\). Similarly, define \(X_J,Y_I,Y_J,Z_I,Z_J\).

Here, without loss of generality, assume \(|X_I| \leq |Y_J|\). Now consider the cut \((X_I,X_J \cup Y_I \cup Y_J \cup Z_I \cup Z_J)\). That is, this is the cut obtained after moving \(Y_I \cup Z_I\) from the \(i\) side to the \(j\) side. We can show that the capacity of this cut is at most the capacity of the original cut. What is important here is that in \(U\), the weight of internal vertices decreases as we approach the root. Keeping this in mind, the “gain” (the decrease in cut capacity) from moving \(Y_I\) is at least \(|Y_I| \times (|Y_J|-|X_I|) \times w_k\), which is at least \(0\). Considering the movement of \(Z_I\), since all the internal vertices determining the cost are ancestors of \(k\), only the number of vertices in \(X_I\) and \(Y_J\) matters, so the gain here is also at least \(0\). Combining these, we can show that the capacity of the new cut is at most that of the original cut.

From the above, there exists an optimal cut in which \(Y,Z\) are entirely placed on the \(j\) side, so let us take one such cut.

Next, let \(h\) be the LCA of all vertices on the \(i\) side of the cut. Here, \(j\) is outside the subtree of \(h\). Among the children of \(h\), let \(X\) be the ones containing \(i\), \(Y\) be the ones not containing \(i\), and \(Z\) be outside the subtree of \(h\). Define \(X_I,X_J,Y_I,Y_J,Z_J\) as in the previous section. Since \(Z_I\) is empty, we do not use it.

Now, let us consider the following two cuts.

• \((X_I,X_J \cup Y_I \cup Y_J \cup Z_J)\)
• \((X_I \cup X_J \cup Y_I \cup Y_J, Z)\)

Let us consider the differences in capacity between these two cuts and the original cut. First, for a leaf \(v\) outside \(Z_J\), consider the sum of the capacities of the edges between \(v\) and all vertices within \(Z_J\); this is constant regardless of \(v\). Let \(R\) denote this value.

Let us consider the first cut. This is the cut obtained by moving \(Y_I\) to the \(j\) side. The gain from this move is at least \(((|X_J|+|Y_I|-|X_I|)\times w_h+R) \times |Y_I|\).

Next, let us consider the second cut. This is the cut obtained by moving \(X_J,Y_J\) to the \(i\) side. In this case, the gain is at least \(((X_I+Y_I)\times w_h-R) \times (|X_J|+|Y_J|)\).

It is impossible for both of these values to be negative. If the second cut achieves a gain of at least \(0\), then we obtain a cut of the desired form. If the first cut achieves a gain of at least \(0\), then we obtain a cut in which \(h\) is closer to the leaves; by continuing this process, we eventually reach a cut of the target form.

This completes the proof.