洛谷P1196 [NOI2002] 银河英雄传说题解

题目链接：P1196 [NOI2002] 银河英雄传说

题意：

一共有 \(n=30000\) 个人，给定 \(Q ~(1\le Q \le 5\times 10^5)\) 次操作

M i j 表示将 \(i\) 所在队伍拼接到 \(j\) 所在队伍队尾。

C i j 表示询问 \(i,j\) 在队伍中相差多少个人（ \(i,j\) 不算在内）

如果他们不在一个队伍中，请输出 \(-1\) 。

带权并查集模板题，~~欠了快大半年才去研究~~

说实话，以前怎么看都看不懂，现在看就很显然，不知道为什么。

第一个操作显然是可以用并查集维护的（~~难不成你用左偏树？~~）

考虑如何维护第二个操作。注意到并查集其实维护了一个森林。

而带权并查集，实际上就是把普通并查集维护的森林带上了边权。

我们记录两个数组 \(d_i\) 和 \(s_i\) （代码里是 d[] 和 sz[]）

\(d_i\) 表示当前结点到根的距离
\(s_i\) 表示它所在的树的结点个数

void init(int n)
{
    for(int i=1; i<=n; i++)
        f[i]=i, sz[i]=1, d[i]=0;
} // 初始化很好理解吧...

考虑将 \(u\) 所在的树与 \(v\) 所在的树合并。

也就是把 \(u\) 所在队伍拼到 \(v\) 所在队伍的后面。

void merge(int u,int v)
{
    u=find(u); v=find(v); // 找到它们对应的根
    f[u] = v; d[u] += sz[v]; // rt(u) -> rt(v) 连一条边权为 sz[v] 的边
    sz[u] = sz[v] += sz[u]; // rt(v)拼上rt(u)后 sz[rt(v)] 会加上 sz[rt(u)]
}

（ cxy：「第二行」为什么要连上一条边权为 \(s_i\) 的边呢？QAQ）

仔细观察可以发现，\(\mathtt{rt}(u)\) 到 \(\mathtt{rt}(v)\) 之间正好相距（修改前的） \(s_v-1\) 个人

但是为了方便维护，这里连 \(s_v\)

因为如果有个 \(\mathtt{rt}(k)\) 又连上了 \(\mathtt{rt}(u)\) ，它到 \(\mathtt{rt}(v)\) 的距离为 \[ s_u+s_v+s_k-1 \]

注：这里的 \(s\) 均指合并前的大小。

（ cxy：「第三行」又是在干什么呢？QAQ）

这里其实是做了一个边权的前缀和，压缩前的样子可以看下图（ \(U,V\) 指 \(\mathtt{rt}(u),\mathtt{rt}(v)\) ）

请注意，这张图省略了 \(v\) 子树间的边权，实际上每条边都有边权。

不难发现这个边权前缀和的过程其实就是令 \(s_{v} \gets s_{v}+s_{u}\) 。

然后考虑查询操作。

int find(int x)
{
    if(f[x] == x)return x;
    int top = find(f[x]); // x 的 rt，注意这里还没路径压缩
    d[x] += d[f[x]]; // x 的父亲到 rt 的距离已经递归算出来了，所以 x 加上就好了
    sz[x] = sz[top]; // 根据定义显然
    return f[x]=top; // 路径压缩
}

// 主函数内这么写
if(op=='M') merge(x,y);
else
{
    if(find(x)!=find(y))cout << "-1\n"; // 不在同一个树（连通块）里
    else cout << abs(d[x]-d[y])-1 << '\n'; // -1是因为x,y中至少有一个会被算进去
}

（ cxy：为什么要再把 \(x\) 的父亲算一遍什么的啊？QAQ）

因为像上图中 \(\mathtt{rt}(u)\) 连到 \(\mathtt{rt}(v)\) 后，\(u\) 所在子树的 \(d_i\) 显然会变

实际上我们在查询的时候并不知道查询的 \(x\) 是不是被修改过根的

但是如果没被修改，\(d_{\mathtt{rt}(x)}=0\) ，故 d[x] += d[f[x]] 不会有什么影响。

到此为止，本题就做出来了。

时间复杂度 \(O(Q \log n)\) （没有按秩合并那肯定是log咯）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e5+15)

char op;
int n,f[N],sz[N],d[N];
void init(int n)
{
    for(int i=1; i<=n; i++)
        f[i]=i, sz[i]=1, d[i]=0;
}
int find(int x)
{
    if(f[x] == x)return x;
    int top = find(f[x]);
    d[x] += d[f[x]]; sz[x] = sz[top];
    return f[x]=top;
}
void merge(int u,int v)
{
    u=find(u); v=find(v);
    f[u] = v; d[u] += sz[v];
    sz[u] = sz[v] += sz[u];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; init(n);
    for(int i=1,x,y; i<=n; i++)
    {
        cin >> op >> x >> y;
        if(op=='M') merge(x,y);
        else
        {
            if(find(x)!=find(y))cout << "-1\n";
            else cout << abs(d[x]-d[y])-1 << '\n';
        }
    }
    return 0;
}