7.9*树算法设计和井查集树算法设计7.9.1树分为有根树和无根树有根树中有且仅有一个根结点并且默认树中边（分支）是有向边，也称为有向树。无根树实际上是一个连通无环图，没有根结点，树中的边是无向边。本章中的树默认为有根树，无根树看成无向图，在下一章讨论
树分为有根树和无根树。 有根树中有且仅有一个根结点并且默认树中边（分支）是有向边，也 称为有向树。 无根树实际上是一个连通无环图，没有根结点，树中的边是无向边。 本章中的树默认为有根树，无根树看成无向图，在下一章讨论
1.双亲存储结构2.孩子链存储结构根据问题需要选择合适的存储结构3.孩子兄弟链存储结构
1. 双亲存储结构 2. 孩子链存储结构 3. 孩子兄弟链存储结构 根据问题需要选择合适的存储结构
【例7.24】P0J1330-求树中两个结点的最近公共祖先（LCA）：问题描述：有根树是计算机科学和工程中众所周知的数据结构，下图是一棵有根树。在该图中，每个结点标有1～16的整数。结点8是树的根。如果结点x位于根结点到结点V之间的路径中，则结点x是结点V的祖先。注意这里规定一个结点也是自已的祖先，如结点7的祖先有结点8，4，6和7如果结点x是结点y和结点z的祖先，则结点x称为两个不同结点y和z的公共祖先，因此结点8和4是结点16和7的公共祖先。如果x是y和z的共同祖先并且在所有共同祖先中最接近y和z，则结点x被称为结点y和z的最近公共祖先。因此，结点16和7的最近公共祖先是结点4，因为结点4比结点8更靠近结点16和7。编写一个程序，找到树中两个不同结点的最近公共祖先。101116
【例7.24】POJ1330—求树中两个结点的最近公共祖先（LCA）。 问题描述：有根树是计算机科学和工程中众所周知的数据结构，下图是一棵有 根树。在该图中，每个结点标有1～16的整数。结点8是树的根。如果结点x位于根 结点到结点y之间的路径中，则结点x是结点y的祖先。注意这里规定一个结点也是 自己的祖先，如结点7的祖先有结点8，4，6和7。 如果结点x是结点y和结点z的祖先，则结点x称为两个不同结点y和z的公共祖 先，因此结点8和4是结点16和7的公共祖先。如果x是y和z的共同祖先并且在所有共 同祖先中最接近y和z，则结点x被称为结点y和z的最近公共祖先。因此，结点16和7 的最近公共祖先是结点4，因为结点4比结点8更靠近结点16和7。编写一个程序，找 到树中两个不同结点的最近公共祖先。 8 5 9 6 4 7 10 1 15 11 16 2 3 12 14 13
输入格式：输入由T个测试用例组成。测试用例个数（T）在输入文件的第一行中给出。每个测试用例以整数N的行开始，整数N是树中的结点数，2≤N≤10,000。结点用整数1～N标记。接下来的N-1行中的每一行包含一对表示边的整数，第一个整数是第二个整数的父结点。请注意，具有N个结点的树具有恰好N-1个边。每个测试用例的最后一行包含两个不同的整数，需要计算它们的最近公共祖先。输出格式：为每个测试用例输出一行，该行应包含最近公共祖先结点的编号
输入格式：输入由T个测试用例组成。测试用例个数（T）在输入文件 的第一行中给出。每个测试用例以整数N的行开始，整数N是树中的结点数， 2≤N≤10,000。结点用整数1～N标记。接下来的N-1行中的每一行包含一 对表示边的整数，第一个整数是第二个整数的父结点。请注意，具有N个结 点的树具有恰好N-1个边。每个测试用例的最后一行包含两个不同的整数， 需要计算它们的最近公共祖先。 输出格式：为每个测试用例输出一行，该行应包含最近公共祖先结点 的编号
输入样例：2//表示有2个测试用例161/测试用例1的数据1148 510 165 9468 44101.1361510116 710 216 38 1161216 7//求结点16和7的LCA51/测试用例2的数据2 33 4311535//求结点3和5的LCA输出样例：43
输入样例： 2 //表示有 2个测试用例 16 //测试用例 1的数据 1 14 8 5 10 16 5 9 4 6 8 4 4 10 1 13 6 15 10 11 6 7 10 2 16 3 8 1 16 12 16 7 //求结点16 和 7 的LCA 5 //测试用例 2的数据 2 3 3 4 3 1 1 5 3 5 //求结点 3 和 5 的LCA 输出样例： 43