给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
（qwq）
1.暴搜
即往树根一步一步搜。。。当然这样会妥妥T到飞起（
2.倍增求LCA
首先通过 (x=fa[x][lg[dep[x]-dep[y]]-1]) 来使得(x)的深度与(y)的深度相同
倍增即按照以2为底的幂来增大（啥） 这样就避免一步一步跑T飞啦~
2,4,8,16,32……
首先通过 (x=fa[x][lg[dep[x]-dep[y]]-1]) 来使得(x)的深度与(y)的深度相同
（手证正确性差评）
两次把1写成i……该注意了
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAXN 500005
using namespace std;
struct qwq
{
int t,nex;
};
int tot=0,dep[MAXN],fa[MAXN][22],lg[MAXN],h[MAXN],n,m,s;
qwq e[MAXN<<1];
inline void add(int x,int y)
{
e[++tot].t=y;
e[tot].nex=h[x];
h[x]=tot;
}
void dfs(int f,int fat)
{
dep[f]=dep[fat]+1;
fa[f][0]=fat;
for (int i=1;(1<<i)<=dep[f];i++)//<--(i<<i)惨案
{
fa[f][i]=fa[fa[f][i-1]][i-1];
}
for (int i=h[f];i>0;i=e[i].nex)
{
if (e[i].t!=fat)
dfs(e[i].t,f);
}
}
inline int LCA(int x,int y)
{
if (dep[x]<dep[y])
{
swap(x,y);
}
while (dep[x]>dep[y])
{
x=fa[x][lg[dep[x]-dep[y]]-1];
}
if (x==y)
{
return x;
}
for (int i=lg[dep[x]-1];i>=0;i--)
{
if (fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
inline void init()
{
scanf("%d%d%d",&n,&m,&s);
for (int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
for (int i=1;i<=n;i++)
{
lg[i]=lg[i-1]+(1<<lg[i-1]==i);//<--历史总是惊人的相似
}
}
inline void start()
{
dfs(s,0);
for (int i=1,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
printf ("%d
",LCA(x,y));
}
}
int main()
{
init();
start();
return 0;
}