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

题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式
第一行包含三个正整数 N,M,S分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 N-1 行每行包含两个正整数 x, y，表示 x 结点和 y结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 M 行每行包含两个正整数 a, b，表示询问 a 结点和 b 结点的最近公共祖先。

输出格式
输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。

输入输出样例
输入 #1
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出 #1复制
4
4
1
4
4
说明/提示
对于 30% 的数据，N≤10，M≤10。

对于 70% 的数据，N≤10000，M≤10000。

对于 100% 的数据，N≤500000，M≤500000。

样例说明：

该树结构如下：

第一次询问：2, 4 的最近公共祖先，故为 4。

第二次询问：3, 2的最近公共祖先，故为 4。

第三次询问：3,5 的最近公共祖先，故为 1。

第四次询问：1,2 的最近公共祖先，故为 4。

第五次询问：4,5 的最近公共祖先，故为 4。

故输出依次为 4,4,1,4,4。

这个博客写的很好，看完应该能理解LCA
Vendetta BlogsJVxie的个人博客

模板：

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<iostream>
#include<vector>
#include<set>
#include<stack>
#include<map>
#include<queue>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N=5e5+5;
const int prime=2333317;
const int INF=0x3f3f3f3f3f;
int n,m,s,k,k2;
int head[N],head2[N],pre[N],vis[N],num[N];
struct node
{
    int v,next;
}edge[N*10];
struct Node
{
    int v,next,w;
}se[N*10];
void init()
{
    memset(vis,0,sizeof(vis));
    memset(num,0,sizeof(num));
    memset(head2,-1,sizeof(head2));
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
        pre[i]=i;
    k=k2=0;
}
void add(int u,int v)
{
    edge[k].v=v;
    edge[k].next=head[u];
    head[u]=k++;
}
void add2(int u,int v,int w)
{
    se[k2].v=v;
    se[k2].w=w;
    se[k2].next=head2[u];
    head2[u]=k2++;
}
int Find(int x)
{
    if(x!=pre[x])
    {
        pre[x]=Find(pre[x]);
    }
    return pre[x];
}
void join(int x,int y)
{
    int fx=Find(x);
    int fy=Find(y);
    if(fx!=fy)
        pre[fy]=fx;
}
void dfs(int u)
{
    vis[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(!vis[v])
        {
            dfs(v);
            vis[v]=1;
            join(u,v);
        }
    }
    for(int i=head2[u];i!=-1;i=se[i].next)
    {
        int v=se[i].v;
        int w=se[i].w;
        if(vis[v])
            num[w]=Find(v);
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&s)!=EOF)
    {
        int x,y;
        init();
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            add2(x,y,i);
            add2(y,x,i);
        }
        dfs(s);
        for(int i=1;i<=m;i++)
        {
            printf("%d\n",num[i]);
        }
    }
    return 0;
}