关于洛谷 P3379 【模板】最近公共祖先（LCA）

参考原文
（建议你顺手点个赞????）
首先来介绍一下什么是LCA：

LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科
额~~看不懂没关系，我来举个栗子????，你和小A是表兄弟，LCA就是求你和小A的那个长辈是同一个人；
并且这个人辈分越小越好。

再来举个栗子????：

11和12的LCA为2，4和9的LCA为4，10和6的LCA为2
在这里我讲一下倍增法
就是就当前节点的父亲（我们称为0倍祖宗），爷爷（1倍祖宗），爷爷的父亲（2倍祖宗），爷爷的爷爷~~；
以此类推；

void cl()//par[x][y]表示y的x倍祖宗
{
	for(int k=0;k+1<MAX_LOG_N;k++)
	{
		for(int v=1;v<=a;v++)
		{
			if(par[k][v]<0)
			par[k+1][v]=-1;//在这里我们提前设根节点的父亲为-1；
			else 
			par[k+1][v]=par[k][par[k][v]];
		}
	}
}

接下来就可以开始你的操作了
（敬告读者：快读快写不要少，return 0必需有）

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void out(int a){
   if(a<0) putchar('-'),a/=-1;
   if(a>9) out(a/10);
   putchar(a%10+'0');
}
int a,b,c,d,e,shen[500005],par[20][500005],q1,q2, MAX_LOG_N;
vector<int> q[500005];
void dfs(int v,int p,int d)
{
	par[0][v]=p;
	shen[v]=d;
	for(int i=0;i<q[v].size();i++)
	{
		if(q[v][i]!=p) dfs(q[v][i],v,d+1);
	}
}
void cl()
{
	for(int k=0;k+1<MAX_LOG_N;k++)
	{
		for(int v=1;v<=a;v++)
		{
			if(par[k][v]<0)
			par[k+1][v]=-1;
			else 
			par[k+1][v]=par[k][par[k][v]];
		}
	}
}
int lca(int u,int v)
{
	if(shen[u]>shen[v])
	swap(u,v);
	for(int k=0;k<MAX_LOG_N;k++)
	{
		if(shen[v]-shen[u]>>k&1)
		{
			v=par[k][v];
		}
	}
	if(u==v)
	return u;
	for(int k=MAX_LOG_N-1;k>=0;k--)
	{
		if(par[k][v]!=par[k][u])
		{
			u=par[k][u];
			v=par[k][v];
		}
	}
	return par[0][u];
}
int main()
{
	a=read();b=read();c=read();
    MAX_LOG_N=log(a)/log(2);
	for(int i=1;i<a;i++)
	{
		d=read();e=read();
		q[d].push_back(e);
		q[e].push_back(d);
	}
    dfs(c,-1,0);
    cl();
    for(int i=1;i<=b;i++)
	{
		q1=read();q2=read();
		out(lca(q1,q2));
		putchar('\n');
	}
return 0;
}