题解：P15049 [UOI 2022 II Stage] 图 2

前言

套路题。
目前是双倍经验的最优解和这个题的最优解。
思路

发现有回溯操作，考虑经典转化建出操作树变成可撤销问题，因为有连边操作，所以使用可撤销并查集维护连通性。
维护第 \(k\) 大，我们通常使用值域分块解决，考虑对每个并查集的根维护所在集合内的答案。在可撤销并查集合并的时候合并答案，类似于启发式合并。这样复杂度是 \(O(n\sqrt{n \log n})\)，可以通过。
具体实现可以看代码。
代码

[code]constexpr int N = 5e5 + 2;int n, m, A[N], B[N], fa[N], g, siz[N], ans[N], typ[N], D, K, cnt;int f[N][810];int p[N], hd[N], to[N  m >> g; D = sqrt(n) * 1.5 + 1, K = (n - 1) / D + 1;    for(int i = 1; i  typ;        if(typ == 1) cin >> A >> B, add(i - 1, i);        else if(typ == 2) cin >> A >> B, add(i - 1, i);        else cin >> A, add(A, i);    }       dfs(0);    for(int i = 1; i