银河英雄传说 不使用回溯路径压缩的解法

· · 题解

难以理解路径压缩时的回溯更新？本篇题解将只使用启发式合并的带权并查集解决本题。

首先我们要知道，本题只使用启发式合并的困难在哪里。

在一般的启发式合并中，我们只需要将大小更小的集合合并至大小更大的集合即可。

但在此题中，有一个给定的集合需要按某一权值合并至另一集合，这意味着如果使用普通的启发式合并方式，我们就无法正确维护权值信息。

考虑将集合 x 以权值 v 合并至集合 y 的影响。可以发现，原先所有在集合 x 中的元素都增加了 v 的权值。

而如果我们要将 y 合并至 x，我们可以在 x 上打一个永久化的标记 v，代表 x 及其子树内的点权值全部增加 v。因为 y 子树的权值不会增加，所以连向 x 的边权应该为 x 上标记的相反数。

如果我们要将 x 合并至 y，边权应当先减去 y 上的标记，再增加 v。

具体的合并方式可以看下面的这张图：

代码实现见下。

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;
int n,pre[N],val[N],tag[N],siz[N];
//tag为节点上的标记，val为出边的边权
pair<int,int> find(int x){
    if(pre[x]==x) return {x,tag[x]};
    auto e=find(pre[x]);
    return {e.first,e.second+val[x]+tag[x]};
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=30000;++i) siz[i]=1,pre[i]=i;
    for(int u,v,i=1;i<=n;++i){
        char op; cin>>op>>u>>v;
        if(op=='M'){
            int x=find(u).first,y=find(v).first;
            if(siz[x]>siz[y]){
                pre[y]=x; tag[x]+=siz[y]; val[y]=-tag[x]; 
                siz[x]+=siz[y];
            }
            else{
                pre[x]=y; val[x]=siz[y]-tag[y];
                siz[y]+=siz[x];
            }
        }
        else{
            auto f=find(u),g=find(v);
            if(f.first!=g.first) cout<<-1<<'\n';
            else cout<<abs(f.second-g.second)-1<<'\n';
        }
    }
    return 0;
}