题目描述

题目大意

给你一个森林,接下来有好多个操作,分别是连边和询问两点的LCA。

其中,如果是将点uuu和点vvv连起来,是将uuu的根节点作为连完边后的根。


思考历程

如果这题没有连边操作,那就十分happy了。

想过是否可以用链剖,发现好像不能。

但是,既然有边的修改,那么——

当然是用LCT了!

思考了半天,我想到一个结论:

对于两个点uuu和vvv,它们到rootrootroot的路径之交中,深度最大的,就是它们的LCALCALCA。

所以,我一开始的想法是这样的:

access(u)
将u到root的路径上的所有点打个标记
access(v)
找到v所在splay中带标记的最深的点即LCA

打着打着,突然发现很麻烦。

想一下,access其实就是一个从当前点的splay上沿着虚边往上跳,将虚边改为实边的过程。

access(u),如果再access(v),就可以发现:

过程中修改的最后一个虚边的父亲,必定就是它们的LCA。

原因很显然,因为跳到LCA后,再跳就没了。

我在打access时,总喜欢设一个返回值,这个返回值是最后修改的点(也就是最后修改虚边的父亲)。因为这个点同时也是在过程后,根所在的splay中的根节点。(如果不记录,翻转的时候还需要splay一遍,多浪费啊!)

其实可以发现,就算是uuu和vvv同在一条链上,结果也是正确的。

所以,想要切掉这题,只是一个LCT模板……

还有,对于连通性,直接并查集就好。

时间O(Qlg⁡N)O(Q\lg N)O(QlgN)


题解&正解

题解的做法有两种:

离线做法

有一个神奇的性质:

具体怎么证明,请自行分类讨论,很好证的。

那么我们可以处理出森林最后的样子,随便以一个点为根。

在处理操作的过程中,用并查集记录每个点当时所处的树中的根是谁。

直接利用上面的性质就好,求LCA用倍增或链剖。

时间O(Qlg⁡N)O(Q\lg N)O(QlgN)

在线做法

和上面的做法本质差不多,要用倍增的方法。

在合并两棵树的时候,简单粗暴地将那棵较小的树安在那棵较大的树下面,暴力更新它的倍增数组。

暴力重建的个数不超过Nlg⁡NN \lg NNlgN个,所以时间是O(Qlg⁡2N)O(Q \lg^2 N)O(Qlg2N)。


代码

LCT做法

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100000
int n,m;
int root[MAXN+1];
struct Node{//LCT的节点
Node *fa,*c[2];
bool res,is_root;
inline bool getson() {return fa->c[0]!=this;}
inline void reserve(){
swap(c[0],c[1]);
res^=1;
}
inline void pushdown(){
if (res){
c[0]->reserve();
c[1]->reserve();
res=0;
}
}
inline void push(){
if (!is_root)
fa->push();
pushdown();
}
inline void rotate(){
Node *y=fa,*z=y->fa;
bool k=getson();
fa=z;
if (y->is_root){
y->is_root=0;
is_root=1;
}
else
z->c[y->getson()]=this;
y->c[k]=c[!k];
c[!k]->fa=y;
c[!k]=y;
y->fa=this;
}
inline void splay(){
push();
while (!is_root){
if (!fa->is_root){
if (getson()!=fa->getson())
rotate();
else
fa->rotate();
}
rotate();
}
}
inline Node *access();
inline Node *mroot();
inline void link(Node *v);
} d[MAXN+1];
Node *null=d;
inline Node *Node::access(){
Node *x=this,*y=null;
for (;x!=null;y=x,x=x->fa){
x->splay();
x->c[1]->is_root=1;
x->c[1]=y;
y->is_root=0;
}
return y;//返回最后修改的点
}
inline Node *Node::mroot(){
Node *sr=access();
sr->reserve();
return sr;
}
inline void Node::link(Node *v){
v->mroot()->fa=this;
}
int bcj[MAXN+1];//并查集
int gettop(int x){
if (bcj[x]==x)
return x;
return bcj[x]=gettop(bcj[x]);
}
int main(){
freopen("arrival.in","r",stdin);
freopen("arrival.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i){
d[i].fa=d[i].c[0]=d[i].c[1]=null;
d[i].is_root=1;
}
for (int i=1;i<=n;++i)
bcj[i]=i;
for (int i=1;i<=m;++i)
scanf("%d",&root[i]);
for (int i=1;i<=n-m;++i){
int u,v;
scanf("%d%d",&u,&v);
d[u].link(&d[v]);
bcj[gettop(u)]=gettop(v);
}
for (int i=1;i<=m;++i)
d[root[i]].mroot();
int Q;
scanf("%d",&Q);
for (int i=1;i<=Q;++i){
int op,u,v;
scanf("%d%d%d",&op,&u,&v);
if (op==1){
if (gettop(u)!=gettop(v)){
bcj[gettop(u)]=gettop(v);
d[u].link(&d[v]);
}
}
else{
if (gettop(u)==gettop(v)){
d[u].access();
printf("%d\n",d[v].access()-d);
}
else
printf("orzorz\n");
}
}
return 0;
}

题解做法(离线做法)

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100000
#define MAXQ 100000
int n,m;
int root[MAXN+1];
struct EDGE{
int to;
EDGE *las;
} e[MAXN*2+1];
int ne;
EDGE *last[MAXN+1];
inline void link(int u,int v){
e[++ne]={v,last[u]};
last[u]=e+ne;
}
int bcj[MAXN+1],tmp[MAXN+1];
int gettop(int x){
if (bcj[x]==x)
return x;
return bcj[x]=gettop(bcj[x]);
}
int fa[MAXN+1][17];//倍增数组
int dep[MAXN+1];
void dfs(int);
inline int lca(int,int);
struct Operation{
int ty;
int u,v;
} o[MAXQ+1];
int main(){
freopen("arrival.in","r",stdin);
freopen("arrival.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
bcj[i]=i;
for (int i=1;i<=m;++i)
scanf("%d",&root[i]);
for (int i=1;i<=n-m;++i){
int u,v;
scanf("%d%d",&u,&v);
link(u,v),link(v,u);
bcj[gettop(u)]=gettop(v);
}
for (int i=1;i<=m;++i){
bcj[gettop(root[i])]=root[i];
bcj[root[i]]=root[i];
}
memcpy(tmp,bcj,sizeof bcj);//bcj要用来处理连边时判断是否出现环,所以暂存一下
int Q;
scanf("%d",&Q);
for (int i=1;i<=Q;++i){
scanf("%d%d%d",&o[i].ty,&o[i].u,&o[i].v);
if (o[i].ty==1){
if (gettop(o[i].u)!=gettop(o[i].v)){
bcj[gettop(o[i].v)]=o[i].v;
bcj[o[i].v]=gettop(o[i].u);
link(o[i].u,o[i].v),link(o[i].v,o[i].u);
}
}
}
for (int i=1;i<=m;++i)
if (gettop(root[i])==root[i])
dfs(root[i]);
swap(bcj,tmp);//这样交换只会交换指针,不会交换整个数组
for (int i=1;i<=Q;++i)
if (o[i].ty==1){
if (gettop(o[i].u)!=gettop(o[i].v)){
bcj[gettop(o[i].v)]=o[i].v;
bcj[o[i].v]=gettop(o[i].u);
}
}
else{
int rt=gettop(o[i].u);
if (rt!=gettop(o[i].v)){
printf("orzorz\n");
continue;
}
printf("%d\n",lca(o[i].u,o[i].v)^lca(o[i].u,rt)^lca(o[i].v,rt));
}
return 0;
}
void dfs(int x){
dep[x]=dep[fa[x][0]]+1;
for (int i=1;1<<i<dep[x];++i)
fa[x][i]=fa[fa[x][i-1]][i-1];
for (EDGE *ei=last[x];ei;ei=ei->las)
if (ei->to!=fa[x][0]){
fa[ei->to][0]=x;
dfs(ei->to);
}
}
inline int lca(int u,int v){
if (dep[u]<dep[v])
swap(u,v);
for (int k=dep[u]-dep[v],i=0;k;k>>=1,++i)
if (k&1)
u=fa[u][i];
if (u==v)
return u;
for (int i=16;i>=0;--i)
if (fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}

总结

LCT大法好,比题解的在线做法好多了。

如果题目加上个删边操作……题解的两个方法都做不了,除非有什么变态的改进。

其实LCT也挺好打的,很好手推。

05-19 01:29
查看更多