题解：CF1725I Imitating the Key Tree

happybob · 2025-11-13 21:06:20 · 题解

一眼看过去这个题限制就很多，然后恰好 2n-2 条边也十分奇怪，边权限定 w_1<w_2<\cdots<w_{n-1} 也很诡异。

考虑从小到大依次加入每条边，加入一条边时你需要考虑图上在这两个连通块之间加边。不难注意到你必须恰好在两个连通块之间加两条边，且其中一条边权等于这条树边也就是目前的最大值，而另一条只需要比其小即可。设连通块大小分别为 s_1,s_2，这是第 i 次加边，则贡献是 (s_1s_2)^2(2i-1)，2i-1 含义是另一条边的权值的相对顺序可以在之前的所有边的顺序中任意一个位置插入。

并查集维护，复杂度 O(n \alpha(n))。