题目描述

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

输入输出格式

输入格式：

 

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

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

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 

5 5 43 12 45 11 42 43 23 51 24 5

输出样例#1： 

44144

说明

时空限制：1000ms,128M

数据规模：

对于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

不断跳，跳到一条重链

输出在上面的

不用写线段树

 

 

#include
     
      #include
      
       #include
       
        using namespace std;const int MAXN=2*1e6+10;#define ls k<<1#define rs k<<1|1inline char nc(){    static char buf[MAXN],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;}inline int read(){    char c=nc();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=nc();}    while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}    return x*f;}struct node{    int u,v,nxt;}edge[MAXN];int head[MAXN];int num=1;void AddEdge(int x,int y){    edge[num].u=x;    edge[num].v=y;    edge[num].nxt=head[x];    head[x]=num++;}int fa[MAXN],deep[MAXN],tot[MAXN],son[MAXN],top[MAXN],cnt;int dfs1(int now,int f,int dep){    deep[now]=dep;    fa[now]=f;    tot[now]=1;    int maxson=-1;    for(int i=head[now];i!=-1;i=edge[i].nxt)    {        if(edge[i].v==f) continue;        tot[now]+=dfs1(edge[i].v,now,dep+1);        if(tot[edge[i].v]>maxson) maxson=tot[edge[i].v],son[now]=edge[i].v;    }    return tot[now];}void dfs2(int now,int topf){    top[now]=topf;    if(!son[now]) return ;    dfs2(son[now],topf);    for(int i=head[now];i!=-1;i=edge[i].nxt)        if(edge[i].v!=son[now]&&edge[i].v!=fa[now])            dfs2(edge[i].v,edge[i].v);}int LCA(int x,int y){    while(top[x]!=top[y])    {        if(deep[top[x]]
        
         deep[y]) swap(x,y);    return x;}int main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif    memset(head,-1,sizeof(head));    int N=read(),M=read(),root=read();    for(int i=1;i<=N-1;i++)     {        int x=read(),y=read();        AddEdge(x,y);AddEdge(y,x);    }    dfs1(root,0,1);    dfs2(root,root);    while(M--)    {        int x=read(),y=read();        printf("%d\n",LCA(x,y));    }    return 0;}