LCA，最近公共祖先。
这是在树上的算法，但是为什么我们把它归为图论呢？
因为它对图论太重要了，其实，树也是图，是任意二节点只有一条路径的图。
我们来看一下LCA的栗子：
这就是LCA，很好理解吧！
那问题来了，怎么实现求两点的LCA呢？
其实很简单，用暴力法就可以了。先用树的DFS遍历求出树的深度，在一个一个向父节点搜索，找到一样的就是它们的LCA了！
简单粗暴吧！
大家可能会感到疑惑，真的有这么简单？
是的，是这么简单。来回顾一下问题：怎么实现求两点的LCA，DFS是能求，也好求。但是有一个缺点：太慢。
当我们的树的深度很大时，我们无法承受这巨大的复杂度，所以我们要想办法优化它。
我们先来看一下暴力解法的代码，并确保你理解了。
code
1 #include <bits/stdc++.h> 2 #define MAXN 100005 3 using namespace std; 4 typedef long long ll; 5 int v[MAXN];//标记节点是否被访问 6 int fa[MAXN];//每个节点的父亲节点 7 int depth[MAXN];//每个节点的深度 8 vector<int>g[MAXN];//vector存树 9 void init()//初始化 10 { 11 memset(v,0,sizeof(v)); 12 memset(depth,0,sizeof(depth)); 13 memset(fa,0,sizeof(fa)); 14 for(int i=0;i<MAXN;i++) 15 { 16 g[i].clear(); 17 } 18 } 19 void dfs(int s,int step)//DFS遍历 20 { 21 depth[s]=step; 22 v[s]=1; 23 for(int i=0;i<g[s].size(); i++) 24
