题解 P3379 【【模板】最近公共祖先（LCA）】
不知道为什么没人正式发一个tarjan c++的代码
感觉tarjan比倍增好写的；
就是一个树的dfs后序遍历，代码量感觉要小一些；
只要掌握tarjan的思路的话就很好写了；
与倍增不同，我们要把所有的询问全部记录后再开始进行计算；
我们需要用并查集储存各个点的祖先关系；
我们首先从根节点开始遍历，按照后序遍历的原则，遍历每一个子节点，如果子节点依然有子节点，就一直往下找，直到找到叶节点（设为v）；然后，我们开始寻找看是否有点与v有询问关系，假设我们有一个点u与v有询问关系，我们就看u是否已经被遍历过，如果没有被遍历，则不进行处理，如果被遍历过了，那么二者的LCA就是find（u）；然后，我们返回V的父亲节点（x），并将v合并入以x为祖先的并查集；这时，我们首先会对x的所有子节点按照刚才的方法进行处理，然后我们按照相同的方法对x进行处理，这样将整个树遍历一遍，就可以得到所有需要的LCA；
代码如下：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define de system("pause");
using namespace std;
int fir[500050],to[1000100],ne[1001000];//用来存树
int firp[500500],as[1000050],nep[1001000],ans[1000100];//用来存储询问关系；
int n,m,s,e,q,a,b;
bool vis[500050]; //当前节点是否走过；
int fa[500050];//用于并查集查询；
int f[500010];//用于记录当前节点的父亲节点以便遍历该节点的子节点；
void add(int u,int v) //邻接表存储树
{
e++;
to[e]=v;
ne[e]=fir[u];
fir[u]=e;
}
void app(int x,int y) //邻接表存储询问关系
{
q++;
as[q]=y;
nep[q]=firp[x];
firp[x]=q;
}
int find(int x) //并查集
{
if(x!=fa[x])
{
fa[x]=find(fa[x]);
}
return fa[x];
}
void un(int x,int y) //并查集
{
int xx=find(x);
int yy=find(y);
if(xx!=yy)
{
fa[xx]=yy;
}
}
void tarjan(int x) //tarjan核心，本质就是dfs后序遍历
{
for(int i=fir[x];i;i=ne[i])
{
int t=to[i];
if(t==f[x]) //遍历子节点
{
continue;
}
f[t]=x;
tarjan(t); //继续往下遍历；
un(t,x); //将t合并入x （非常重要）
vis[t]=1; //将t（x的子节点）标记为已走过
}
for(int i=firp[x];i;i=nep[i])
{
int y=as[i]; //查询与x有关的lca询问
if(vis[y]) //如果遍历过，
{
ans[i]=find(y); //那么x与y的最近公共祖先就是find（y）;
}
}
}
inline int read()
{
int ee=0,ff=1;
char ss=getchar();
while((ss<'0'||ss>'9')&&ss!='-')ss=getchar();
while((ss>='0'&&ss<='9')||ss=='-')
{
if(ss=='-')ff=-1;
else ee=ee*10+ss-'0';
ss=getchar();
}
return ee*ff;
}
int main()
{
n=read();m=read();s=read();//题目要求输入
for(int i=1;i<=n-1;i++)
{
a=read();b=read();
add(a,b);add(b,a);// 题目要求输入
}
for(int i=1;i<=m;i++)
{
a=read();b=read(); //题目要求输入，我用邻接表存储询问关系，
app(a,b);app(b,a); //x,y 的公共祖先与 y,x 的公共祖先是一样的，要存双向
}
for(int i=1;i<=n;i++) //并查集常规初始化
{
fa[i]=i;
f[i]=i;
}
tarjan(s); //以s为根节点开始遍历
for(int i=1;i<=m;i++)
{
printf("%d\n",max(ans[2*i],ans[2*i-1]));}//略蠢的储存答案方式 return 0;
} 总感觉我的存储的答案的方式有点蠢，因为我不知道被询问的两个点谁先被询问到，所以我用了一个2*m的数组储存答案，相当于是邻接表存储双向图边权，有兴趣的人可以用我的程序输出ans[1]~ans[2*m]，有更好方法的还请好心人告诉我一声
ps：tarjan纯自学，学计算机就是要有自学的能力，我感觉我写的已经比较详细了，如果邻接表，并查集不懂那就先补补课吧，认真钻研没什么是学不会的