题目链接：https://www.luogu.org/problemnew/show/P3379

题意：LCA模板题。

思路：今天开始学树剖，先拿lca练练。树剖解lca，两次dfs复杂度均为O(n)，每次查询为logn，因此总复杂度为：O(2*n+m*logn)。

代码：

#include
     
      #include
      
       using namespace std;const int maxn=500005;struct node{    int v,next;}edge[2*maxn];int n,m,s,cnt,size[maxn],head[maxn],depth[maxn],son[maxn],fa[maxn],top[maxn];void add(int u,int v){    edge[++cnt].v=v;    edge[cnt].next=head[u];    head[u]=cnt;}void dfs1(int x){    size[x]=1;    depth[x]=depth[fa[x]]+1;    for(int i=head[x];i;i=edge[i].next){        int v=edge[i].v;        if(v==fa[x]) continue;        fa[v]=x;        dfs1(v);        size[x]+=size[v];        if(!son[x]||size[son[x]]
       
        depth[top[y]]) x=fa[top[x]];            else y=fa[top[y]];        }        printf("%d\n",depth[x]