题解：CF2162G Beautiful Tree

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

首先考虑增量构造，瞪了 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

存在其他做法。