P1196

发表于 分类于
[NOI2002] 银河英雄传说

[NOI2002] 银河英雄传说

边带权并查集。

令 $d(x)$ 表示 $x$ 之前的战舰数量。

我们在每次 Get 的时候，先维护 $d(x)$ 再进行路径压缩，就可以维护正确的数据。

每次 Merge 的时候，$x$ 一定是接在 $y$ 后面的，也就是说，$x$ 的根一定要成为 $y$ 的子节点。

同时，原先与 $y$ 相连的所有点的 $d$ 都未改变，而与 $x$ 相连的却会改变。

显然我们不用急着把所有与 $x$ 相连的点的 $d$ 全部改变，只要把 $x$ 的根的 $d$ 变成 $y$ 所连的并查集的大小即可（前方有多少战舰）。然后以后每次 Get 的时候后面的点会懒惰维护的。

因此我们需要再多维护一个并查集的大小，没了。

时间复杂度 $O(m\log n)$。并查集嘛，这个 $\log$ 就随意对待了。。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=3e4;

ll T;
ll fa[N+5],d[N+5],siz[N+5];

inline ll Get(ll x) {
  if(x==fa[x]) return x;ll rt=Get(fa[x]);d[x]+=d[fa[x]];return fa[x]=rt;
}

inline void Merge(ll x,ll y) {
  x=Get(x);y=Get(y);fa[x]=y;d[x]=siz[y];siz[y]+=siz[x];
}

int main() {

  for(ll i=1;i<=N;i++) {fa[i]=i;siz[i]=1;}

  T=read();

  while(T--) {
    char op[5];cin>>op;
    if(op[0]=='M') {
      ll x,y;x=read();y=read();Merge(x,y);
    }
    if(op[0]=='C') {
      ll x,y;x=read();y=read();
      if(Get(x)==Get(y)) {writeln(abs(d[x]-d[y])-1);}
      else {writeln(-1);}
    }
  }

  return 0;
}