POJ 1330 Nearest Common Ancestors LCA

http://poj.org/problem id=1330

给你一棵树，让你求LCA（Least Common Ancestors 最近公共祖先）

去年（好吧，就前几天，时间真的好快）数据结构上机考就是考了LCA，结果不懂。。。T T ，来研究下

有个tarjan算法正在研究中，然后看到有大牛的思路。。。

然后跟着大牛的思路写了一遍。。

tarjan等我研究出来了在写。。

思路就是用父节点数组表示法，建立树，然后从b或者a开始找跟结点（这里假设从b），把所有经过的结点全部标记为访问过，然后a也这样做，当遇到访问过的就跳出循环，这时候就是所求的LCA了

#include
  
   
#include
   
     const int MAXN=10000+10; int fa[MAXN]; bool vis[MAXN]; int main() { int T; scanf("%d",&T); while(T--) { memset(vis,0,sizeof(vis)); memset(fa,-1,sizeof(fa)); int n; scanf("%d",&n); int a,b; for(int i=1;i