观察：当 $n>1$ 时，度数序列 $\{d_i\}$ 合法当且仅当 $d_i\ge 1$ 且 $\sum d_i=2n-2$。
如果存在 $a_i=-1$，只需要度数的最小值之和不超过 $2n-2$ 即可。否则还需要满足最小值之和和 $2n-2$ 的差是 $m$ 的倍数。
构造完度数序列之后，按照度数从大到小，每次在之前的点当中为当前点选一个父亲即可。时间复杂度 $O(n)$。
QOJ.ac
QOJ
Discussion #1219 for Problem #17168. Sweet Remainders!
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2026-03-06 01:30:47
Last updated: 2026-03-06 01:30:52
题解
Comments
No comments yet.