part 3

• T1T2秒了
• T2
• 一个很重要的性质 在最小生成树上一定存在一种最优环只有一条非树边 可以证明如果不满足的话它就不是最小生成树了
• 我这里写的是无脑树链剖分+线段树解决但实际上还有更加优秀的做法
• 我们对非树边进行排序，从小到大加入，那么第一次找到的环就是当前点的最优解，再并查集缩点即可，沾一下实现代码

for (int i = 1; i <= m; ++i)if (~e[i].z) {int x = gf(e[i].x), y = gf(e[i].y);while (x != y) {if (dp[x] < dp[y]) swap(x, y);if (ans[x] == -1) ans[x] = e[i].z;if (ans[f[x]] == -1) ans[f[x]] = e[i].z;fa[x] = f[x], x = gf(x);}}