Functional graph and construction Draw a directed edge . Every vertex has outdegree one. Each weakly connected component contains exactly one directed cycle, with trees feeding into it.
For a cycle of length at least three, keep every edge except one as a friendship. A two-cycle consists of opposite preferences between the same two people, so keep just one undirected edge. Discard self-loops. Keep every edge outside cycles. Finally, connect the resulting forest components with arbitrary edges to obtain a tree.
DSU implements this construction directly: for each , add the edge only if its endpoints currently belong to different sets, then unite them. Finally connect vertex to vertices still belonging to other sets.
Proof of optimality A term with is always zero. Every non-self preference outside cycles costs at least one. Consider a directed cycle of length . In any final tree, concatenate the paths visiting its vertices in cycle order and returning to the start. Every edge of the minimal subtree spanning these vertices is crossed at least twice by this closed walk. Since that subtree contains distinct vertices, it has at least edges. The cycle's total distance is therefore at least . Passing through vertices of other functional components cannot invalidate this bound.
In the construction, a cycle with has preferences at distance one and one preference at distance , attaining . In a two-cycle both preferences have distance one. Every non-cycle preference also has distance one. Connecting the components does not change the unique internal paths. Thus all lower bounds are attained simultaneously.
The minimum is:
Remove indegree-zero vertices with a queue. Exactly the cycle vertices remain. Traverse each remaining cycle to measure its length and evaluate the formula in . Opposite preferences in a two-cycle share one friendship edge, but both terms still count in the objective.
Complexity and verification The construction takes time and space. Graph depth may reach , so the reference avoids recursive DFS. The optimum is between and . An arbitrary incorrect candidate tree can have a distance sum as large as , so the checker uses signed 64-bit sums. Vertex indices, degrees, and depths are at most .
The checker validates edge count, endpoints, and the tree property, then computes actual distances using LCA and compares their sum with an independently computed optimum. Its time and space complexities are .
Subtask 1 enumerates all labeled trees using Prüfer sequences. BFS from every vertex evaluates a tree in time, yielding total time and at most space. This is sufficient for . Subtask 4 uses the functional graph and DSU.
Solution written by GPT6