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

44144

#include <iostream>#include <cstdio>#include <cmath>//maybe my English is not very good using namespace std;const int M = 5e5 + 1;int n,m,s;int num; int deep[M],h[M];bool vs[M];int jumps[M][21];int p;struct A{    int next;    int to;}t[M<<1];inline int read() //optimize{    int x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘)    {        if(ch==‘-‘) f=-1;        ch=getchar();    }    while(ch>=‘0‘&&ch<=‘9‘)    {        x=x*10+ch-‘0‘;        ch=getchar();    }    return x*f;}void ADD(int x,int y) //connect the x and the y{    num++;    t[num].to=y;    t[num].next=h[x];    h[x]=num;}void Dfs(int u){    for(int i=h[u];i!=-1;i=t[i].next)    {        int v=t[i].to; //u‘s next side        if(deep[v] == 0) //if v is not visited        {            deep[v]=deep[u]+1; //deep+1            jumps[v][0]=u; //u is v‘s dad            Dfs(v); //continue Dfs                    }    }}void steps(){    p=int(log(n)/log(2)+0.001); //find the biggest    for(int i=1;i<=p;i++) //the Limit        for(int j=1;j<=n;j++)            jumps[j][i]=jumps[jumps[j][i-1]][i-1];//the j jump 2^i can get to the (first jump 2^(i-1),then jump 2^i-1 can get to)//eh...I will speak in Chinese.//because 倍增 is use 次方的形式 increase}int LCA(int a,int b){    //We let the b‘s deep is small    if(deep[a]<deep[b]) swap(a,b);    for(int i=p;i>=0;i--)    {//first let the a jump to the b‘s deep        if(deep[jumps[a][i]]>=deep[b])        a=jumps[a][i];    }    if(a == b) return b; //if the b is them‘s LCA , return b    for(int i=p;i>=0;i--) //jump together    {        if(jumps[a][i]!=jumps[b][i])        a=jumps[a][i],b=jumps[b][i]; //update    }    return jumps[a][0]; }int main(){    //s is the root    n=read();m=read();s=read();    for(int i=1;i<=n;i++) h[i]=-1;    int x,y;    for(int i=1;i<n;i++)    {        x=read();y=read();        //connect the x and the y        ADD(x,y);        ADD(y,x);    }    deep[s]=1; //this is too important !!!    //if you don‘t think so ,"//" it.     //and then you will know    Dfs(s); //Dfs the root(s)    steps(); //find the steps    int a,b;    while(m--)    {        a=read();b=read();        printf("%d\n",LCA(a,b));    }    return 0;}

#include<iostream>#include<cmath>#include<algorithm>#include<cstring>#include<cstdio>#include<stdio.h>#include<vector>#define maxn 500500using namespace std;///隶属邻接表 struct Edge{                    //邻接表的结构体     int from,to;}edges[2*maxn];                 //边要乘2，因为是无向图 ； int first[maxn],next[2*maxn];   //同理； int read(){                        //读入优化，可以照着这个模板来写，这个还算写的比较好看。     int re=0;    char ch=getchar();    while (ch<‘0‘ || ch>‘9‘) ch=getchar();    while (ch>=‘0‘ && ch<=‘9‘){         re=re*10+ch-‘0‘;         ch=getchar();    }    return re;}//////////////////////////////////////////////////全局变量 int n,m;int root;int height[maxn];float log2n;//////////////////////////////////////////////////////////隶属LCA的全局变量 int f[maxn][20];// int have[maxn];                           //have，有没有找过，这都是套路 。 void dfs(int u,int h){                 //u代表点的标号，h代表高度。     int v;    height[u]=h;    for(int i=1;i<=log2n;i++) {        if(h<=(1<<i)) break;              //由于i是从小到大计算的，故（1<<i）>=h 时可直接退出。请务必想清楚是<=  还是=。        f[u][i] = f[ f[u][i-1] ][i-1]; //动规计算。同样也是一切倍增算法的核心。     }    int k=first[u];    while(k!=-1){        v=edges[k].to;        if(!have[v]) {            have[v]=1;                    f[v][0]=u;                 //将要找的下一个点的父节点标为当前处理的节点u。             dfs(v,h+1);        }        k=next[k];    }}int require_LCA(int a,int b){    int da=height[a],db=height[b];//第一步，将a，b两点移到同样的高度，只动高度大的那个点而不动高度小的那个点。     if(da!=db) {        if(da<db){                   //保证a的高度是大于b的高度的。             swap(a,b);            swap(da,db);        }        int d=da-db;        for(int i=0;i<=log2n;i++)             if( (1<<i) & d) a=f[a][i]; //这里的位运算可以减少代码量                                       //考虑到d是一个定值，而（1<<i）在二进制中只有第（i+1）位是1；                                        //那么d与（1<<i）如果某一位为1，那么表示可以向上移动，                                        //如果此时不移动，那么i增大了后就无法使height[a]==height[b]了     }//第二步,找到某个位置i，在这个位置时，f[a][i]!=f[b][i],但再向上移动一步，a，b相同了 //从log2n开始从大到小枚举i，如果超过了a，b的高度，则令i继续减小//如果没有超过a，b的高度，那么就判断移动了后会不会让a==b，//是，则i继续减小，否则，令此时的a=f[a][i],b=f[b][i];     if(a==b) return b;    int i=0;    for(i=log2n;i>=0;i--) {        if(height[ f[a][i] ]<0) continue;        if( f[a][i]==f[b][i] ) continue;        else a=f[a][i],b=f[b][i];        //顺便一提，在第二步任何地方没有break；                                       //我就是因为在这里写了一个break，然后找了我两个小时啊。     }        return f[a][0];}////////////////////////////////////据说从主函数开始阅读是个好习惯。 int main(){//    freopen("in2.txt","r",stdin);    n=read();m=read();root=read();    memset(first,-1,sizeof(first));    memset(next,-1,sizeof(next));    int s,t;    int dsd=2*(n-1);    for(int i=1;i<=dsd;i+=2) {        s=read();t=read();      //读入优化。         edges[i].from=s;        edges[i].to=t;        edges[i+1].from=t;        edges[i+1].to=s;        next[i]=first[s];        first[s]=i;        next[i+1]=first[t];        first[t]=i+1;    }    // 以上是邻接表，在此不再赘述。     log2n=log(n)/log(2)+1;        //C++计算log是自然对数，我们要用的以2为底的对数，故要除以log(2);                                   //对无理数加上1或是0.5是个好习惯，可以减小误差；     memset(have,0,sizeof(have));    memset(height,0,sizeof(height));    memset(f,-1,sizeof(f));    have[root]=1;                //fa[][]和height[]要在dfs理进行计算，不然根本找不到某个非根节点的父亲是谁;     dfs(root,1);                    for(int i=1;i<=n;i++){        for(int j=0;j<=log2n;j++) {            if(height[i] <=(1<<j) ) break;        }    }    for(int i=0;i<m;i++) {      //应对要求进行求解。         s=read();t=read();        int y=require_LCA(s,t);        printf("%d\n",y);    }    return 0;}

#include <iostream>#include <cstdio>#define _(ch) ch=read()                    //便于读入 using namespace std;const int S = 500001;bool f[S];                                 //dfs 标记int n,m,s;int fa[S];                                 //并查集 int num,h[S];                             //邻接表 int deep[S];                             //深度 int sum[S];                             //子结点个数 int dad[S];                             //链头元素 struct B{    int to,next;}t[S<<1];inline int read()                         //optimize{    int x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘)    {        if(ch==‘-‘) f=-1;        ch=getchar();    }    while(ch>=‘0‘&&ch<=‘9‘)    {        x=x*10+ch-‘0‘;        ch=getchar();    }    return x*f;  }void ADD(int x,int y)                     //connect the x and the y{    num++;    t[num].to=y;    t[num].next=h[x];    h[x]=num;}inline int Find(int x)//find the root (重链‘s top){return fa[x] == x ? x : fa[x] = Find(fa[x]);}inline void Unions(int a,int b){                                        //union(搭重链)    /*int f1=Find(a);    int f2=Find(b);    if(f1!=f2)    {        fa[f1]=f2;    }*/    fa[Find(b)]=Find(a);}inline void dfs(int p)//D is the (结点){//calc every D‘s son D//每个结点的深度     f[p]=true;    int maxx=0;                            //寻找子节点中拥有子结点个数最多的节点编号     sum[0]=-1;                            //0号没有子结点    for(int j=h[p];j;j=t[j].next)     {                                    //进行遍历         int v=t[j].to;        if(f[v]) continue;        deep[v]=deep[p]+1;        dad[v]=p;                        //p is v‘s dad         dfs(v);                         //continue dfs        if(sum[v] > sum[maxx]) maxx=v;     //update        sum[p]+=sum[v]+1;//        p的子结点数 = p 的以‘v‘为根的子树的结点数目加上‘v‘这个点(即+1)    }    if(maxx) Unions(p,maxx);            //if updated     //that means find the (重链) succeed}inline int jump(int p)                     //find p can jump to  {    int top=Find(p);                     //(重链)‘s top     if(top == p) return dad[p];//    如果p所处于的链的链头就是自己,也就是说,已经位于链的top处,所以只能够跳到他的父结点的位置,//    所以直接return it‘s dad,即跳一步到达父结点处 //    说白了就是说,一定要跳!!!     return top;                            //其余情况就返回链头就好(就是当前结点跳到了链头位置) }inline int Lca(int a,int b)             //Lca {    while(a!=b)                         //当两点不相等的时候就开始跳     {        if(Find(a)==Find(b))             //如果它们位于同一条重链上           return deep[a]<deep[b] ? a:b; //直接返回深度较浅的那个点         int ja=jump(a),jb=jump(b);        if(deep[ja] > deep[jb])            //如果a跳了之后没有到达b跳了之后的深度             a=ja;                        //就选取深度较深的点跳         else            b=jb;    }    return a;}int main(){    _(n),_(m),_(s);    int x,y;    for(int i=1;i<n;i++)    {        _(x),_(y);        ADD(x,y),ADD(y,x);        fa[i]=i;                        //顺便初始化一下并查集     }    fa[n]=n;                             //有一个没有进行初始化的并查集,进行初始化     deep[s]=1;                             //根结点的深度设置为1,非常重要!!!!     dfs(s);                                //寻找子节点个数,位于哪一条重链上     while(m--)    {        _(x),_(y);        printf("%d\n",Lca(x,y));    }    return 0;}