考虑对于$n-1$个数$a_{i}$，函数$f(x)=\frac{\sum_{i=1}^{n-1}(x-a_{i})^{2}}{n-1}$的最小值恰在$x=\frac{\sum_{i=1}^{n-1}a_{i}}{n-1}$取到（根据二次函数显然），因此题意可以理解为任选实数$b$并最小化$\frac{\sum_{i=1}^{n-1}(b-a_{i})^{2}}{n-1}$（本来要求$b$为平均值）
可以暴力枚举$b$并将边权从$d$变为$(b-d)^{2}$求最小生成树，但由于$b$为实数，并不能直接枚举
（为了方便，以下约定两条边边权若相同，编号小的更小）
对于最小生成树而言，所选的边事实上仅取决于边的大小关系，考虑两条边$i$和$j$（其中$i<j$）满足$i$在$j$前面当且仅当$x\le \lfloor\frac{w_{i}+w_{j}}{2}\rfloor$，以此法即产生了$o(n^{4})$个区间，每一个区间内大小关系都相同
（每一段都是左端点为圆括号，右端点为中括号）
对于每一段，以$b$作为参数来表示边权，比较时使用区间内任意数字即可，最后即求一个二次函数区间（其实也可以忽略区间限制）最小值，即可做到$o(n^{6})$的复杂度，可以通过
（以下可能有一些口胡）
更进一步的，考虑每一次权值变化即将两条边优先级交换，且交换的两边优先级相邻（不妨假设为两边为$i$和$j$，其中交换前$i$优先级较大），此时不难证明——
如果修改最小生成树，则必然是$i$本来在最小生成树中被删除，$j$本来不在最小生成树中被加入（其余边不修改）
（证明考虑kruskal贪心的过程并分类讨论即可）
因此只需要判定能否替换即可，用按秩合并并查集维护，复杂度为$o(n^{4}\log n)$
view code