[普及+/提高]A104751题解

题意（形式化）

给定 $n$ 个点，进行 $m$ 次连边操作后进行 $q$ 次询问，询问两个点 $u,v$ 它们最早在第几次你连边操作后联通，如果至始至终没有联通，输出 $-1$。

思路

注意到如果 $a$ 与 $b$ 联通，且 $b$ 与 $c$ 联通，那么 $a$ 肯定与 $c$ 联通，相当于朋友的朋友是朋友，考虑并查集。

我原先的思路是每次合并连通块时，根节点存现在的操作数，但是后来发现这样会破坏原有的信息，于是在每次连边后需要一个新点来当两点的父节点，这个新点存联通时间。换句话说，这个新点存的是：“左子树所代表的连通块与右子树所代表的连通块，连通的最早时间。（注意每次连边都会需要一个新结点，所以实际上要用到 $n+m$ 个结点）但是为了不破坏树原来的结构，我们无法进行路径压缩，这也导致了时间复杂度爆炸，无法通过。于是考虑我们在并查集的基础上新建个树，这个树才存未更改的情况，并查集则正常路径压缩。最后，如果我们想求两个结点何时联通，只需LCA查找其父节点即可（原因显然），需特判两个点为同一点以及两点不联通的情况。

后来我才知道原来这叫做Kruskal 重构树。当时为了不TLE重复尝试了15次，都快绝望了。

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 400005;
const int Log = 20;
int fa[N] , sz[N] , Time[N] , n , m , q;
int up[Log][N] , maxTime[Log][N] , deep[N];
vector<int> ch[N];
void dfs(int now , int D){
    deep[now] = D;
    for(auto i : ch[now]){
        up[0][i] = now;
        maxTime[0][i] = Time[i];
        dfs(i , D + 1);
    }
}
void into(){
    for(int i = 1;i <= n + m;i ++){
        fa[i] = i;
        sz[i] = 1;
        Time[i] = 0;
    }
}
int Find(int x){
    if(fa[x] == x) return x;
    else{
        fa[x] = Find(fa[x]);
    }
    return fa[x];
}
int query(int u , int v){
    if(u == v) return 0;
    int ans = 0;
    if(deep[u] < deep[v]) swap(u , v);
    int diff = deep[u] - deep[v];
    for(int k = 0;k < Log;k ++){
        if(diff & (1 << k)){
            ans = max(ans , maxTime[k][u]);
            u = up[k][u];
        }
    }
    if(u == v) return ans;
    for(int k = Log - 1;k >= 0;k --){
        if(up[k][u] != up[k][v]){
            ans = max(ans , maxTime[k][u]);
            ans = max(ans , maxTime[k][v]);
            u = up[k][u];
            v = up[k][v];
        }
    }
    ans = max(ans , maxTime[0][u]);
    ans = max(ans , maxTime[0][v]);
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    into();   
    int node_max = n;
    for(int i = 1;i <= m;i ++){
        int x , y;
        cin >> x >> y;
        int rx = Find(x) , ry = Find(y);
        if(rx == ry) continue;
        if(sz[rx] < sz[ry]) swap(rx , ry);
        node_max ++;
        fa[rx] = node_max;
        fa[ry] = node_max;
        sz[node_max] = sz[rx] + sz[ry];
        Time[rx] = i;
        Time[ry] = i;
        ch[node_max].push_back(rx);
        ch[node_max].push_back(ry);
    }
    for(int i = 1;i <= node_max;i ++){
        if(fa[i] == i){
            up[0][i] = i;
            maxTime[0][i] = 0;
            dfs(i , 1);
        }
    }
    for(int k = 1;k < Log;k ++){
        for(int i = 1;i <= node_max;i ++){
            up[k][i] = up[k-1][up[k-1][i]];
            maxTime[k][i] = max(maxTime[k-1][i] , maxTime[k-1][up[k-1][i]]);
        }
    }
    for(int i = 1;i <= q;i ++){
        int u , v;
        cin >> u >> v;
        if(u == v){
            cout << 0 << '\n';
            continue;
        }
        int ru = Find(u) , rv = Find(v);
        if(ru != rv){
            cout << -1 << '\n';
            continue;
        }
        cout << query(u , v) << '\n';
    }
    return 0;
}