洛谷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;
}