# 倍增和 LCA 的模板

# 一、倍增

倍增及成倍增长，其时间复杂度为$O(nlogn)$，初始化为$O(nlogn)$，查询为$O(1)$

至于倍增例题，没有特别好的只用倍增的例题，大部分倍增都是直接有应用了，最多的还是$LCA$，具体代码可以在下面$LCA$ 的部分查看

# 二、LCA（即最近公共祖先）

最基础的$LCA$ 基本上可以说是倍增算法的应用（当然如果你是究极大佬直接用树剖当我没说）,$LCA$ 每次查询为$logn$，整体时间复杂度还是倍增的时间复杂度，为$O(nlogn)$

例题：最近公共祖先

Code:

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=500001;
int fa[N][21];
int in[N];
int h[N];
int n,m,s,ans[20001][20001];
vector <int > son[N];
void dfs(int pre,int cur)
{
    fa[cur][0]=pre;
    h[cur]=h[pre]+1;
    for(int i=1;i<20;i++)
    	fa[cur][i]=fa[fa[cur][i-1]][i-1];
    for(int i=0;i<son[cur].size();i++)
    	if(son[cur][i]!=pre)
    		dfs(cur,son[cur][i]);
    return;
}
int lca(int a,int b)
{
    if(h[a]<h[b])
    	swap(a,b);
    for(int i=19;i>=0;i--)
    {
        if(h[a]-(1<<i)>=h[b])
        	a=fa[a][i];
    }
    if(a==b)
    	return a;
    for(int i=19;i>=0;i--)
    {
        if(fa[a][i]!=fa[b][i])
        	a=fa[a][i],b=fa[b][i];
    }
    return fa[a][0];
}
int main()
{
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=n-1;i++)
    {
            int a,b;
            scanf("%d %d",&a,&b);
            son[a].push_back(b);
            son[b].push_back(a);
    }
    int root=s;
    dfs(0,root);
    for(int i=1;i<=m;i++)
    {
	    int q1,q2;
	    scanf("%d %d",&q1,&q2);
	    if(q1>20000 || q2>20000)
		{
			printf("%d\n",lca(q1,q2));
			continue; 
		}
	    if(ans[q1][q2]!=0)
	    	printf("%d\n",ans[q1][q2]);
	    else
	    {
	    	ans[q1][q2]=ans[q2][q1]=lca(q1,q2);
	    	printf("%d\n",ans[q1][q2]);
		}
	}
    return 0;
}