「NOI模拟赛3.13」远行Hike - LCT+并查集 | Bill Yang's Blog

「NOI模拟赛3.13」远行Hike - LCT+并查集

题目大意

    Miranda生活的城市有$N$个小镇,一开始小镇间没有任何道路连接。随着经济发现,小镇之间陆续建起了一些双向的道路但是由于经济不太发达,在建设过程中,会保证对于任意两个小镇,最多有一条路径能互相到达。有的时候Miranda会从某个小镇开始进行徒步旅行,每次出发前,她都想选择一个她能到达的最远的小镇作为终点,并且她在行走过程中是不会走回头路的,为了估算这次旅行的时间,她会需要你告诉她这次旅行的时间会是多少呢?可以假设通过每条道路都需要单位时间,并且 Miranda 不会在小镇停留。
    强制在线


题目分析

简单地说,这是一道要求动态维护树最长链的题目。

根据最长链合并的原则:
两棵树最长链合并时,最长链只可能在原来四个端点中产生。

因此我们可以用并查集来维护每棵树的最长链端点与长度。
每次使用LCT提取出树中的链,比较链长(即size)确定最长链,然后记入并查集中。

数据范围有点大,大常数LCT+$4$倍查询会有点卡,$2s$开O2不是很虚。


代码

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
inline int max(int a,int b) {
if(a>b)return a;
return b;
}
const int maxn=300005;
struct Tree {
int father,child[2];
bool rev;
int size;
};
struct Link_Cut_Tree {
Tree tree[maxn];
stack<int>S;
#define fa(x) tree[x].father
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define rev(x) tree[x].rev
bool isroot(int index) {
return ls(fa(index))!=index&&rs(fa(index))!=index;
}
bool checkson(int index) {
return rs(fa(index))==index;
}
void push_down(int index) {
if(!rev(index))return;
swap(ls(index),rs(index));
rev(ls(index))^=1;
rev(rs(index))^=1;
rev(index)=0;
}
void push_up(int index) {
if(index)tree[index].size=tree[ls(index)].size+tree[rs(index)].size+1;
}
void rotate(int index) {
int father=fa(index),grand=fa(father),side=checkson(index);
if(!isroot(father))tree[grand].child[checkson(father)]=index;
tree[father].child[side]=tree[index].child[side^1];
fa(tree[father].child[side])=father;
fa(father)=index;
tree[index].child[side^1]=father;
fa(index)=grand;
push_up(father);
push_up(index);
}
void splay(int index) {
S.push(index);
for(int i=index; !isroot(i); i=fa(i))S.push(fa(i));
while(!S.empty())push_down(S.top()),S.pop();
for(int father; !isroot(index); rotate(index)) {
father=fa(index);
if(!isroot(father))rotate(checkson(index)==checkson(father)?father:index);
}
}
void access(int index) {
for(int son=0; index; son=index,index=fa(index)) {
splay(index);
rs(index)=son;
push_up(index);
}
}
void reverse(int index) {
access(index);
splay(index);
rev(index)^=1;
}
void link(int x,int y) {
reverse(x);
fa(x)=y;
}
void split(int x,int y) {
reverse(x);
access(y);
splay(y);
}
} lct;
int n,q,type,lastans,father[maxn],Dist[maxn],from[maxn],to[maxn];
int Get_Father(int x) {
if(father[x]==x)return x;
return father[x]=Get_Father(father[x]);
}
int update(int x,int y,int& ansa,int& ansb) {
int ans=Dist[x];
ansa=from[x],ansb=to[x];
if(Dist[y]>ans)ansa=from[y],ansb=to[y],ans=Dist[y];
lct.split(from[y],from[x]);
if(lct.tree[from[x]].size-1>ans) {
ans=lct.tree[from[x]].size-1;
ansa=from[x],ansb=from[y];
}
if(from[y]!=to[y]) {
lct.split(to[y],from[x]);
if(lct.tree[from[x]].size-1>ans) {
ans=lct.tree[from[x]].size-1;
ansa=from[x],ansb=to[y];
}
}
if(from[x]==to[x])return ans;
lct.split(from[y],to[x]);
if(lct.tree[to[x]].size-1>ans) {
ans=lct.tree[to[x]].size-1;
ansa=to[x],ansb=from[y];
}
if(from[y]!=to[y]) {
lct.split(to[y],to[x]);
if(lct.tree[to[x]].size-1>ans) {
ans=lct.tree[to[x]].size-1;
ansa=to[x],ansb=to[y];
}
}
return ans;
}
int main() {
type=Get_Int();
n=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++)from[i]=to[i]=father[i]=i;
for(int i=1; i<=q; i++) {
int opt=Get_Int();
if(opt==1) {
int x=Get_Int(),y=Get_Int();
if(type)x^=lastans,y^=lastans;
int fx=Get_Father(x),fy=Get_Father(y),a,b;
lct.link(x,y);
int ans=update(fx,fy,a,b);
father[fx]=fy;
Dist[fy]=ans,from[fy]=a,to[fy]=b;
} else {
int x=Get_Int();
if(type)x^=lastans;
int fx=Get_Father(x);
lct.split(from[fx],x);
lastans=lct.tree[x].size-1;
if(from[fx]!=to[fx]) {
lct.split(to[fx],x);
lastans=max(lastans,lct.tree[x].size-1);
}
printf("%d\n",lastans);
}
}
return 0;
}
0%