倍增求LCA-白红宇

倍增求LCA

阅读量：5009 次

发布时间：2019-06-12

本文共 1358 字，大约阅读时间需要 4 分钟。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
               10 #define ll long long11 #define inf 101058054012 #define DB double13 using namespace std;14 inline int read()15 {16 int x=0,w=1;char ch=0;17 while(!isdigit(ch)){ if(ch=='-') w=-1;ch=getchar();}18 while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();19 return x*w;20 }21 int buf[60];22 void write(int x)23 {24 if(x<0) putchar('-'),x=-x;25 buf[0]=0;26 while(x) buf[++buf[0]]=x%10,x/=10;27 if(!buf[0]) buf[0]=1,buf[1]=0;28 while(buf[0]) putchar('0'+buf[buf[0]--]);29 }30 int n,m,h[1000000],s,tot;31 struct po{ int u,v,last;}a[1000000];32 int f[500002][30],dep[500005];33 void add(int u,int v)34 {35 tot++;a[tot].v=v;36 a[tot].last=h[u];h[u]=tot;37 a[tot].u=u;38 }39 void dfs(int u)40 {41 for(int i=h[u];i;i=a[i].last)42 {43 int to=a[i].v;44 if(dep[to]==0)45 {46 dep[to]=dep[u]+1;47 f[to][0]=u;48 dfs(to); 49 }50 } 51 }52 void YU()53 {54 for(int j=1;(1<
               
                <=n;j++)55 for(int i=1;i<=n;i++)56 f[i][j]=f[f[i][j-1]][j-1];57 } 58 int lca(int x,int y)59 {60 if(dep[x]
                
                 =0;j--)65 if(f[x][j]!=f[y][j]) x=f[x][j],y=f[y][j];66 //cout<
                 
                  <<" "<
                  
                   <