下载掌阅APP，畅读海量书库
立即打开
题目描述（POJ1330）： 一棵树如下图所示，每个节点都标有{1, 2, …, 16}的整数，节点8是树根。若节点 x 位于根和 y 之间的路径中，则 x 是 y 的祖先，节点也是自己的祖先。8、4、10和16是16的祖先，8、4、6和7是7的祖先。若 x 是 y 的祖先和 z 的祖先，则 x 被称为 y 和 z 的公共祖先，因此8和4是16和7的公共祖先。若 x 是 y 和 z 的公共祖先并且在它们的公共祖先中最接近 y 和 z ，则 x 被称为 y 和 z 的最近公共祖先，16和7的最近公共祖先是4。若 y 是 z 的祖先，则 y 和 z 的最近公共祖先是 y ，4和12的最近公共祖先是4。编写一个程序，找到树中两个不同节点的最近公共祖先。
输入： 第1行包含一个整数 T ，表示测试用例的数量。每个测试用例的第1行都包含整数 N （2≤ N ≤10,000），表示树中的节点数。节点用1～ N 标记。接下来的 N -1行，每行都包含一对表示边的整数，第1个整数是第2个整数的父节点（有 N 个节点的树则恰好有 N -1条边）。每个测试用例的最后一行都包含两个不同的整数，求其最近公共祖先。
输出： 对每个测试用例，都单行输出两个节点的最近公共祖先。
题解： 由于本题数据量不大，所以可以暴力求解最近公共祖先LCA。
（1）初始化父节点fa[ i ]= i ，访问标记flag[ i ]=0。
（2）从 u 向上标记到树根。
（3） v 向上，第1个遇到的带有标记的节点即为 u 、 v 的最近公共祖先。
