原题链接

中文简化版：

对于一个大小为 的有标号无根树（标号 ），记其边集为 ，定义其权值为

给定 ，构造一棵树，满足其权值 为完全平方数。

• 。

---

首先考虑增量构造，瞪了 1 min 后感觉没有前途。

然后考虑调整法，先把所有点连到 上，则树的权值为 ，记 。

若 ，则构造完毕。

否则，容易想到将权值调整到 ，显然 是小于 的，在 足够大时小于 。因此有很直接的思路：

• 当 为偶数时，可以调整 连接的点；
• 当 为奇数时，可以调整 连接的点为 ，然后调整 连接的点。

这里还有一些边界条件，可以在 时把目标权值换为 ，显然需要增加的权仍小于 。

然后 较小的时候可能没法保证这个增量一定是小于 的，特判即可。

懒得 Copy 代码了，给个提交链接吧。

存在其他做法。

---

std 做法惊为天人。

• 他说，要让 ；
• 他说，不妨令 ；
• 他说，让 与 相连，让 与 相连，让 与 相连。
• 他说，对于 ，构造完毕。
• 他说，对于 ，仍可以构造，但这里空太小，写不下。