# Title Description

For example, given a tree with multiple forks, the nearest common ancestor of two specified points is requested.

# Input format:

The first row contains three positive integers N, M and S, which respectively represent the number of nodes in the tree, the number of queries and the serial number of the root node of the tree.

Next, each row of N-1 contains two positive integers x and y, indicating that there is a direct connection between X and Y nodes (data guarantee can form a tree).

Next, each row of row M contains two positive integers a and b, indicating the nearest common ancestor of query a and b nodes.

# Output format:

The output contains M lines, and each line contains a positive integer, which is the result of each query in turn.

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

4
4
1
4
4

# thinking

As its name implies, it is the template of lca. I'll save my lca template~

# Offline Tarjan

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=500000+7;
int pre[N],first[N],first2[N],tot,tot2;
int n;
struct edge
{
int v,next;
} e[2*N];
struct Query
{
int v,w,next;
} query[2*N];

{
e[tot].v=v;
e[tot].next=first[u];
first[u]=tot++;
}

{
query[tot2].v=v;
query[tot2].w=-1;
query[tot2].next=first2[u];
first2[u]=tot2++;
}

int find(int x)
{
return x==pre[x]?x:pre[x]=find(pre[x]);
}
void mix(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
pre[fy]=fx;
}

int lca(int u,int fa)
{
for(int i=first[u]; ~i; i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
lca(v,u);
pre[v]=u;
}
vis[u]=1;
for(int i=first2[u]; ~i; i=query[i].next)
{
int v=query[i].v;
if(vis[v])
query[i].w=find(v);
}
}

void init()
{
mem(first,-1);
mem(first2,-1);
mem(vis,0);
tot=0;
tot2=0;
for(int i=1; i<=n; i++)
pre[i]=i;
}

int main()
{
int m,s,u,v;
scanf("%d%d%d",&n,&m,&s);
init();
for(int i=1; i<n; i++)
{
scanf("%d%d",&u,&v);
}
for(int i=1; i<=m; i++)
{
scanf("%d%d",&u,&v);
}
lca(s,pre[s]);
for(int i=0; i<tot2; i++)
if(query[i].w!=-1)
printf("%d\n",query[i].w);
return 0;
}

# Online multiplication

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=500000+7;

int n,m,s;
int tot;
int first[N],d[N],p[N][21];

struct edge
{
int v,next;
} e[2*N];

{
e[tot].v=v;
e[tot].next=first[u];
first[u]=tot++;
}

void dfs(int u,int fa)
{
d[u]=d[fa]+1;
p[u][0]=fa;
for(int i=1; (1<<i)<=d[u]; i++)
p[u][i]=p[p[u][i-1]][i-1];
for(int i=first[u]; ~i; i=e[i].next)
{
int v=e[i].v;
if(v!=fa)
dfs(v,u);
}
}

int lca(int a,int b)
{
if(d[a]>d[b]) swap(a,b);//Make sure a is above point b
for(int i=20; i>=0; i--)
if(d[a]<=d[b]-(1<<i))
b=p[b][i];  //Move b to the same depth as a
if(a==b) return a;
for(int i=20; i>=0; i--)
{
if(p[a][i]==p[b][i])
continue;
else
a=p[a][i],b=p[b][i];//Jump up together
}
return p[a][0];
}

void init()
{
tot=0;
mem(first,-1);
mem(d,0);
mem(p,0);
}
int main()
{
init();
int a,b;
scanf("%d%d%d",&n,&m,&s);
for(int i=1; i<n; i++)
{
scanf("%d%d",&a,&b);