题解 P3379 【【模板】最近公共祖先（LCA）】
小菜鸟
·
·
题解
看着LCT解法还比较少，讲得也不算详细，我来水一篇？
事实上，LCT解法相当好理解。
我们把LCA分为两类
一类是两点中有一点为LCA，如图中3\;7
一类是两点都不是LCA，如图中4\;7
容易发现，第一类情况中，较浅的点在较深的点到根的路径上。
这时将其中一点access，判断另一点是否在同一实链上即可。如图：
第二类情况中，可以先将点a access，再将点b access。
这时我们发现，LCA正是a所在实链顶端的父亲。如图，先access(7)
然后access(4)
于是就做完了。。。
```cpp
template<typename Value_type,typename Functor>
std::pair<bool,typename link_cut_tree<Value_type,Functor>::iterator>
link_cut_tree<Value_type,Functor>::least_common_ancestor(const iterator& siter,const iterator& eiter)
{
Node* sptr=siter.ptr;
Node* eptr=eiter.ptr;
// if(!split(sptr,eptr))return std::make_pair(0,iterator(NULL));//在保证连通时不判断以减小常数
access(sptr);
Node *now1=sptr,*now2=eptr;
while(!now1->is_root())now1=now1->ftr;
while(!now2->is_root())now2=now2->ftr;
if(now1==now2)return std::make_pair(1,iterator(eptr));//判断同一实链
access(eptr);
now1=sptr,now2=eptr;
while(!now1->is_root())now1=now1->ftr;
while(!now2->is_root())now2=now2->ftr;
if(now1==now2)return std::make_pair(1,iterator(sptr));
return std::make_pair(1,iterator(now1->ftr));//此时now1就是sptr所在splay的根
}
```
完整代码如下（开O2最强3个点900+ms卡过）
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
//#define MEMPOOL
template<typename Value_type,typename Functor>
class LCT_splay
{
public:
struct Node;
Node* __new_node(const Value_type&);
#ifdef MEMPOOL
private:
Node mem_pool[1<<20];
int tot;
#endif
};
template<typename Value_type,typename Functor>
struct LCT_splay<Value_type,Functor>::Node
{
Value_type val,sum;
Node* ftr;
Node* ch[2];
// Node*& lc;
// Node*& rc;
#define lc ch[0]
#define rc ch[1]
bool rev;
Node(const Value_type& v=Value_type()):
val(v),
sum(v),
ftr(NULL),
// lc(ch[0]),
// rc(ch[1]),
rev(0) {ch[0]=ch[1]=NULL;}
void reverse();
void push_down();
void push_all();
void maintain();
bool is_root();
void rotate();
void splay();
};
template<typename Value_type,typename Functor>
void
LCT_splay<Value_type,Functor>::Node::reverse()
{
rev^=1;
}
template<typename Value_type,typename Functor>
void
LCT_splay<Value_type,Functor>::Node::push_down()
{
if(!rev)return;
rev=0;
Node* ptr=lc;
lc=rc;
rc=ptr;
if(lc!=NULL)lc->reverse();
if(rc!=NULL)rc->reverse();
}
template<typename Value_type,typename Functor>
void
LCT_splay<Value_type,Functor>::Node::push_all()
{
if(!is_root())this->ftr->push_all();
push_down();
}
template<typename Value_type,typename Functor>
void
LCT_splay<Value_type,Functor>::Node::maintain()
{
Functor func;
sum=func(func(lc!=NULL?lc->sum:Value_type(),val),rc!=NULL?rc->sum:Value_type());
}
template<typename Value_type,typename Functor>
bool
LCT_splay<Value_type,Functor>::Node::is_root()
{
return ftr==NULL||(ftr->lc!=this&&ftr->rc!=this);
}
template<typename Value_type,typename Functor>
void
LCT_splay<Value_type,Functor>::Node::rotate()
{
Node *nftr=ftr,*gftr=ftr->ftr;
bool is_rc=nftr->rc==this;
bool is_rf=gftr!=NULL?gftr->rc==nftr:0;
ftr=gftr;
if(!nftr->is_root())gftr->ch[is_rf]=this;
nftr->ch[is_rc]=this->ch[!is_rc];
if(this->ch[!is_rc]!=NULL)this->ch[!is_rc]->ftr=nftr;
nftr->ftr=this;
this->ch[!is_rc]=nftr;
nftr->maintain();
maintain();
}
template<typename Value_type,typename Functor>
void
LCT_splay<Value_type,Functor>::Node::splay()
{
push_all();
while(!is_root())
{
Node *nftr=ftr,*gftr=ftr->ftr;
if(nftr->is_root())rotate();
else
{
if((gftr->lc==nftr)^(nftr->lc==this))rotate();
else nftr->rotate();
rotate();
}
}
}
template<typename Value_type,typename Functor>
typename
LCT_splay<Value_type,Functor>::Node*
LCT_splay<Value_type,Functor>::__new_node(const Value_type& v)
{
#ifdef MEMPOOL
if(tot==1<<20)
{
fprintf(stderr,"Error:No enough memory\n");
return NULL;
}
mem_pool[tot++].val=v;
return mem_pool+tot-1;
#else
return new Node(v);
#endif
}
template<typename Value_type,typename Functor>
class link_cut_tree:public LCT_splay<Value_type,Functor>
{
typedef typename LCT_splay<Value_type,Functor>::Node Node;
private:
void access(Node*);
void make_root(Node*);
Node* find_root(Node*);
bool split(Node*,Node*);
public:
struct iterator;
iterator make_node(const Value_type&);
bool link(const iterator&,const iterator&);
bool cut(const iterator&,const iterator&);
std::pair<bool,Value_type> query(const iterator&,const iterator&);
std::pair<bool,iterator> least_common_ancestor(const iterator&,const iterator&);
void set_root(const iterator&);
bool modify(iterator,const Value_type&);
};
template<typename Value_type,typename Functor>
struct link_cut_tree<Value_type,Functor>::iterator
{
private:
Node* ptr;
friend class link_cut_tree;
public:
Value_type operator*()const{return ptr->val;}
iterator(Node* p=NULL):ptr(p) {}
iterator(const iterator& iter):ptr(iter.ptr) {}
};
template<typename Value_type,typename Functor>
void
link_cut_tree<Value_type,Functor>::access(Node* ptr)
{
for(Node* nptr=NULL;ptr!=NULL;nptr=ptr,ptr=ptr->ftr)
{
ptr->splay();
ptr->rc=nptr;
ptr->maintain();
}
}
template<typename Value_type,typename Functor>
void
link_cut_tree<Value_type,Functor>::make_root(Node* ptr)
{
access(ptr);
ptr->splay();
ptr->reverse();
}
template<typename Value_type,typename Functor>
typename
link_cut_tree<Value_type,Functor>::Node*
link_cut_tree<Value_type,Functor>::find_root(Node* ptr)
{
access(ptr);
ptr->splay();
while(ptr->lc!=NULL)ptr->push_down(),ptr=ptr->lc;
ptr->splay();
return ptr;
}
template<typename Value_type,typename Functor>
bool
link_cut_tree<Value_type,Functor>::split(Node* sptr,Node* eptr)
{
make_root(sptr);
if(find_root(eptr)!=sptr)return 0;
eptr->splay();
return 1;
}
template<typename Value_type,typename Functor>
typename
link_cut_tree<Value_type,Functor>::iterator
link_cut_tree<Value_type,Functor>::make_node(const Value_type& v)
{
return iterator(LCT_splay<Value_type,Functor>::__new_node(v));
}
template<typename Value_type,typename Functor>
bool
link_cut_tree<Value_type,Functor>::link(const iterator& siter,const iterator& eiter)
{
Node* sptr=siter.ptr;
Node* eptr=eiter.ptr;
make_root(sptr);
if(find_root(eptr)==sptr)return 0;
sptr->ftr=eptr;
return 1;
}
template<typename Value_type,typename Functor>
bool
link_cut_tree<Value_type,Functor>::cut(const iterator& siter,const iterator& eiter)
{
Node* sptr=siter.ptr;
Node* eptr=eiter.ptr;
make_root(sptr);
if(find_root(eptr)!=sptr||eptr->ftr!=sptr||eptr->lc!=NULL)return 0;
eptr->ftr=NULL;
sptr->lc=NULL;
sptr->maintain();
return 1;
}
template<typename Value_type,typename Functor>
std::pair<bool,Value_type>
link_cut_tree<Value_type,Functor>::query(const iterator& siter,const iterator& eiter)
{
Node* sptr=siter.ptr;
Node* eptr=eiter.ptr;
if(!split(sptr,eptr))return std::make_pair(0,Value_type());
return std::make_pair(1,eptr->sum);
}
template<typename Value_type,typename Functor>
std::pair<bool,typename link_cut_tree<Value_type,Functor>::iterator>
link_cut_tree<Value_type,Functor>::least_common_ancestor(const iterator& siter,const iterator& eiter)
{
Node* sptr=siter.ptr;
Node* eptr=eiter.ptr;
// if(!split(sptr,eptr))return std::make_pair(0,iterator(NULL));
access(sptr);
Node *now1=sptr,*now2=eptr;
while(!now1->is_root())now1=now1->ftr;
while(!now2->is_root())now2=now2->ftr;
if(now1==now2)return std::make_pair(1,iterator(eptr));
access(eptr);
now1=sptr,now2=eptr;
while(!now1->is_root())now1=now1->ftr;
while(!now2->is_root())now2=now2->ftr;
if(now1==now2)return std::make_pair(1,iterator(sptr));
return std::make_pair(1,iterator(now1->ftr));
}
template<typename Value_type,typename Functor>
void
link_cut_tree<Value_type,Functor>::set_root(const iterator& iter)
{
Node* ptr=iter.ptr;
make_root(ptr);
}
template<typename Value_type,typename Functor>
bool
link_cut_tree<Value_type,Functor>::modify(iterator iter,const Value_type& v)
{
Node* ptr=iter.ptr;
if(ptr==NULL)return 0;
ptr->splay();
ptr->val=v;
ptr->maintain();
return 1;
}
#undef lc
#undef rc
template<typename Argument_type,typename Result_type>
class Nop
{
public:
Result_type operator()(const Argument_type& x,const Argument_type& y)const
{
return 0;
}
};
link_cut_tree<int,Nop<int,int> > my_LCT;
link_cut_tree<int,Nop<int,int> >::iterator iters[500005];
char gc()
{
static char buf[1<<16],*p1=buf,*p2=buf;
if(p1==p2)
{
p2=(p1=buf)+fread(buf,1,1<<16,stdin);
if(p1==p2)return EOF;
}
return *p1++;
}
#define getchar gc
template<typename T>
void read(T& x)
{
bool f=0;
x=0;
char c=getchar();
while(c<'0'||c>'9')f|=(c=='-'),c=getchar();
while(c>='0'&&c<='9')x=x*10+(c^48),c=getchar();
}
template<typename T>
void write(T x)
{
if(x<0)std::putchar('-'),x=-x;
if(x>=10)write(x/10);
putchar(x%10^48);
}
int main()
{
int n,m,s;
read(n),read(m),read(s);
for(int i=1;i<=n;++i)
{
iters[i]=my_LCT.make_node(i);
}
for(int i=1;i<n;++i)
{
int u,v;
read(u),read(v);
my_LCT.link(iters[u],iters[v]);
}
my_LCT.set_root(iters[s]);
for(int i=0;i<m;++i)
{
int u,v;
read(u),read(v);
write(*(my_LCT.least_common_ancestor(iters[u],iters[v]).second));
putchar('\n');
}
}
```
$LCT$大法好！！！（破音