BZOJ 4668 -- 冷战

发表于 | 更新于 | 分类于 | 评论数：

摘要

在线，连接两点，求两点最早何时连接

题面

解

启发式合并建树

深度 log

暴力求路径最大值

记得维护深度

Code

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <algorithm>
#include <vector>

using std::vector;
using std::swap;
using std::max;

const int MAXN=500011;

int N, M;

vector<int> Mem[MAXN];
int F[MAXN], Size[MAXN], Val[MAXN];
int Dep[MAXN];

int Cnt;
int Ans;

int Find(int a){
	return a==F[a]?a:Find(F[a]);
}

void Merge(int a, int b){
	a=Find(a);b=Find(b);
	if(a==b)	return;
	if(Size[a]>Size[b])	swap(a, b);
	F[a]=b;Val[a]=Cnt;Size[b]+=Size[a];
	for(int i=0, s=(int)Mem[a].size(), p;i<s;++i){
		p=Mem[a][i];
		++Dep[p];
		Mem[b].push_back(p);
	}
}

void Ask(int a, int b){
	Ans=0;
	if(Find(a)==Find(b)){
		while(a!=b){
			if(Dep[a]>Dep[b])	swap(a, b);
			Ans=max(Ans, Val[b]);b=F[b];
		}
	}
}

int main(){
	
	scanf("%d%d", &N, &M);
	
	for(int i=1;i<=N;++i)	{F[i]=i;Size[i]=1;Mem[i].push_back(i);}
	
	for(int i=1, t, a, b;i<=M;++i){
		scanf("%d%d%d", &t, &a, &b);
		a^=Ans;b^=Ans;
		if(t==0){
			++Cnt;
			Merge(a, b);
		}
		else{
			Ask(a, b);
			printf("%d\n", Ans);
		}
	}
	
	
	return 0;
}

/*
5 9
0 1 4
1 2 5
0 2 4
0 3 4
1 3 1
0 7 0
0 6 1
0 1 6
1 2 6

*/