LCA：倍增

memset(p,-,sizeof(p));

inline void dfs(int u)

{

  for (int i=head[u];i!=-;i=e[i].next)

  {

     int v=e[i].v;

     if (deep[v]==)

     {

       deep[v]=deep[u]+;

       p[v][]=u;

       dfs(v);

     }

  }

}

void init()

{

   for (int j=;(<<j)<=n;j++)

   for (int i=;i<=n;i++)

   if (p[i][j-]!=-)

   p[i][j]=p[p[i][j-]][j-];

}

//deep[1]的初始为1

int lca(int a,int b)

{

   int i,j;

   if (deep[a]<deep[b]) swap(a,b);

   for (i=;(<<i)<=deep[a];i++);

   i--;

   for (j=i;j>=;j--)

   if (deep[a]-(<<j)>=deep[b])

   a=p[a][j];

   if (a==b) return a;

   for (j=i;j>=;j--)

   {

     if (p[a][j]!=-&&p[a][j]!=p[b][j])

     {

       a=p[a][j];

       b=p[b][j];

     }

   }

   return p[a][];

}