DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

I need ㅠ

Back to problem

Editorial

Functional graph and construction Draw a directed edge i→Pii\to P_ii→Pi​. 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 (i,Pi)(i,P_i)(i,Pi​), add the edge only if its endpoints currently belong to different sets, then unite them. Finally connect vertex 111 to vertices still belonging to other sets.

Proof of optimality A term with Pi=iP_i=iPi​=i is always zero. Every non-self preference outside cycles costs at least one. Consider a directed cycle of length L≥2L\geq2L≥2. 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 LLL 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 L≥3L\geq3L≥3 has L−1L-1L−1 preferences at distance one and one preference at distance L−1L-1L−1, attaining 2(L−1)2(L-1)2(L. 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:

OPT=#{i:Pi≠i}+∑directed cycles Cmax⁡(0,∣C∣−2).\mathrm{OPT}=\#\{i:P_i\neq i\}+\sum_{\text{directed cycles }C}\max(0,|C|-2).OPT=#{i:Pi​

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 O(N)O(N)O(N). Opposite preferences in a two-cycle share one friendship edge, but both terms still count in the objective.

Complexity and verification The construction takes O(Nα(N))O(N\alpha(N))O(Nα(N)) time and O(N)O(N)O(N) space. Graph depth may reach NNN, so the reference avoids recursive DFS. The optimum is between 000 and 2N−2. 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 O(Nlog⁡N)O(N\log N)O(NlogN).

Subtask 1 enumerates all NN−2N^{N-2}NN−2 labeled trees using Prüfer sequences. BFS from every vertex evaluates a tree in O(N2)O(N^2)O(N2) time, yielding O(NN−2N2)O(N^{N-2}N^2) total time and at most space. This is sufficient for . Subtask 4 uses the functional graph and DSU.

Solution written by GPT6

L−1L-1L−1
2(L−1)2(L-1)2(L−1)
−
1)
=
i}+
directed cycles C∑​max(0,∣C∣−
2).
2N-2
2N−2
N(N−1)<2.5⋅1011N(N-1)<2.5\cdot10^{11}N(N−1)<2.5⋅1011
NNN
O
(
NN−2
N2
)
O(N2)O(N^2)O(N2)
N≤7N\leq7N≤7