题解：CF2162G Beautiful Tree

weilycoder · 2025-11-03 16:35:59 · 题解

体感上是绿的，但是构造题可能方差比较大。

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

然后考虑调整法，先把所有点连到 1 上，则树的权值为 S=\frac{(n+2)(n-1)}{2}，记 m=\left\lceil\sqrt{S}\right\rceil。

若 m^2=S，则构造完毕。

否则，容易想到将权值调整到 m^2，显然 m^2-S 是小于 \sqrt{2}n+O(1) 的，在 n 足够大时小于 2\left(n-1\right)。

当 m^2-S 为偶数时，可以调整 2 连接的点；

当 m^2-S 为奇数时，可以调整 3 连接的点为 2，然后调整 2 连接的点。

这里还存在一些边界条件，可以在 m^2-S\leqslant 7 时把目标权值换为 \left(m+1\right)^2，显然可以保证增加的权仍小于 \sqrt{2}n+O(1)。

然后 n 较小的时候可能没法保证这个增量一定是小于 2\left(n-1\right) 的，特判即可。

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

https://codeforces.com/contest/2162/submission/347214819

存在其他做法。