LCA【模板】-白红宇

LCA【模板】

阅读量：4599 次

发布时间：2019-06-09

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

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 #define N 10015 6  7 using namespace std; 8  9 vector
         
          vec[N];10 int n,a,b,m,deep[N],dad[N][100];11 12 int LCA(int x,int y)13 {14     if(deep[x]>deep[y]) swap(x,y);15     for(int i=20;i>=0;i--)16         if(deep[dad[y][i]]>=deep[x]) y=dad[y][i];17     if(x==y) return x;18     for(int i=20;i>=0;i--)19         if(dad[x][i]!=dad[y][i])20         x=dad[x][i],y=dad[y][i];21     return dad[x][0];22 }23 24 void DFS(int x)25 {26     deep[x]=deep[dad[x][0]]+1;27     for(int i=0;dad[x][i];i++)28         dad[x][i+1]=dad[dad[x][i]][i];29     for(int i=0;i

倍增

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 using namespace std; 6  7 const int N(10005); 8 vector
         
          vec[N]; 9 int n,q,x,y;10 int size[N],deep[N],top[N],dad[N];11 12 void DFS(int x)13 {14     size[x]=1; deep[x]=deep[dad[x]]+1;15     for(int i=0;i
          
           deep[y]) swap(x,y);42     return x;43 }44 45 int main()46 {47     scanf("%d",&n);48     for(int i=1;i