看着题解一脸懵，我来发一个自己的想法。
题解曰:当x-sq*sq同余sq时，答案是2sq+2，否则为2sq+3
但显然sq*sq和sq是同奇偶的，上面的条件等价于n%2是几（逃）
下面是正题。
题目要让树的节点数尽量小。也就是说，我们构造树之后，要让原式尽量大。
考虑有s+1个节点的路径x~y：对于任意节点u，它的贡献为dis(u,x)-dis(u,y)
如图，对于任意一点u，只有一条路径可以抵达路径xy，否则显然会形成一个环，违反树的性质。
令ux，uy路径抵达xy于v，那么dis(u,x)-dis(u,y)=(uv+xv)-(uv+yv)=xv-yv
又v在路径xy上，xv+yv为路径长度，那么在路径长度为定值情况下，要想让xv-yv最大，取xv=长度，yv=0即可。如果要想存在路径u->y->x,u一定在下图的子树中
对于子树每一个节点都对答案产生路径长度的贡献。答案为路径长*子树大小，树点数为路径长+子树大小+1。由于和同近积大，这两个值取相同的时候原式最大。
因此我们的大方向是：取路径长大约为sqrt(x)左右，子树大小为sqrt(x)左右。
然后回到原来的问题。
令s=sqrt(x)向下取整。（x=原式，要用原式倒推树大小）
如果x是平方数，显然取2s+1。因为在树大小2s+1时，x取极值，树小一些，显然x也更小。
否则，我们去先考虑和x相近的根号值s,s+1。
2s+1的答案显然已经不可能了。必须加点维持精准贡献。
虽然有了大方向，但由于我们需要精确的贡献，容易想到令v在xy内部，产生小但精确的贡献。
发现v每次移动，会造成xv，yv一个+1一个-1，差永远是2。
如图，当v在以下节点的贡献：
因为差是2，画图后想到分类奇偶。
因为n<(s+1)*2,得到n-s^2<=2s。
如果s为奇数：
若x为奇数：
如果路径长度为s，那么在s最优情况构造s^2贡献后还需要偶数的贡献（x奇-s*s奇=偶）,显然至少两次贡献，（2s+1）+2=2s+3;
如果路径长度为s+1，由于(s+1)^2是偶数，所以在s+1最优情况构造(s+1)^2贡献后还需要奇数贡献。而偶数长度路径上不存在奇数贡献（如图），舍弃。
若x为偶数
需要奇数的贡献。如果需要的贡献<=s，那么直接加，2s+1+1=2s+2个点。（因为使用s+1至少+3个点，舍）
否则贡献>s，当路径长为s时，直接加至少要用三个节点，也就是2s+4个点。
但是此时可以在s+1最优情况构造(s+1)^2贡献后上减去贡献，减去的贡献=(s+1)^2-s^2-原来的贡献=2s+1-原来的贡献，化简后贡献<s+1且为偶数，存在于路径长为s+1的单次贡献中，直接删除一次原来的最大贡献换成本贡献，也就是s+1最优情况构造(s+1)^2贡献后的树大小2s+3。
如果s为偶数
若x为奇数：
需要加的贡献是奇数，路径长度为s时显然不存在，考虑s+1。
减去的贡献=(s+1)^2-s^2-原来的贡献=2s+1-原来的贡献，在22s之间，可以也至少用两个1s的奇数贡献加起来。因此为2s+1+2=2s+3。
若x为偶数：
和s为奇数时类似，贡献<=s时贡献存在于路径单次贡献，直接加，2s+2
x>s时拆成两个，2s+3。也可以换成(s+1)的情况，但一旦s+1就至少2s+3，不考虑。
整理一下，发现仅当x为偶数，贡献<=s的时候2s+2,否则2s+3。
然后还有一个问题，虽然根据大方向在这个范围左右，为什么一定在s~s+1范围选择？
我具体也没有仔细分析，大概的想法是对于其他的任何路径长度和s~s+1和它同奇偶的相比，奇偶性导致的加减应该不会变，因为答案范围的变化最多为1，而和同近积大中最优无序解就一组，选择其他的一定会带来至少一个节点，所以答案不优。
如果需要更加具体，可以设t为路径长度，分类奇偶性讨论一下，取最优解。
京公网安备 11010502036488号