Steven_MengのBlog

传送门

注意到一个性质,如果加入的边$$已经在连通块里面,发现连通块任意两点都是联通的,于是加入边并不会对答案有任何影响,我们就不加入这一条边。

于是发现这张图在任意时刻都是一个森林,森林就比较好办,考虑记录加入边的时间$tim[]$,于是答案即是$\max\{ tim[w] ,w \in route(u,v)\}$,$route(u,v)$表示$u,v$之间的路径,于是从$u,v$两点分别往上跳并且记录最大值,跳到$lca$为止。

考虑到这样会超时,不妨考虑启发式合并,于是每次查询均摊$\log (n)$,可以AC。

注意异或不要少了。

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
55
56
57
58
59
60
#include <bits/stdc++.h>
#define MAXN 500005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
namespace BCJ{
static int fa[MAXN],sz[MAXN],dep[MAXN],tim[MAXN];
inline void Init(int n){
for (int i=1;i<=n;++i) fa[i]=i,sz[i]=1;
}
int Find(int i){
return fa[i]==i?i:Find(fa[i]);
}
int InitDep(int i){
return (fa[i]==i)?(dep[i]):(dep[i]=(InitDep(fa[i])+1));
}
inline void Merge(int t,int u,int v){
u=Find(u),v=Find(v);
if (u==v) return ;
if (sz[u]<sz[v]) swap(u,v);//v -> u
sz[u]+=sz[v];
fa[v]=u;
tim[v]=t;//连边时间
}
inline int Query(int u,int v){
if (InitDep(u)<=InitDep(v)) swap(u,v);
int ans=0;
while (dep[u]>dep[v]) ans=max(ans,tim[u]),u=fa[u];
if (u==v) return ans;
while (u!=v) ans=max(ans,max(tim[u],tim[v])),u=fa[u],v=fa[v];
return ans;
}
}
using namespace BCJ;
int main(){
int n=read(),m=read();
Init(n);
int lstans=0,cnt=0;
while (m--){
int opr=read(),u=read()^lstans,v=read()^lstans;
if (opr==0) {
Merge(++cnt,u,v);
}
else {
if (Find(u)!=Find(v)) printf("%d\n",lstans=0);
else printf("%d\n",lstans=Query(u,v));
}
}
}

 评论