{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 数据结构中的树,在计算机科学中是非常重要的,例如我们来看看下面这棵树: \n \u003cbr\u003e \n \u003cbr\u003e\u003cimg src\u003d\"CDN_BASE_URL/a4cf40017a91cfbd4f81b13b267ec9ee?v\u003d1626029022\"\u003e\n \u003cimg SRC\u003d\"CDN_BASE_URL/a4cf40017a91cfbd4f81b13b267ec9ee?v\u003d1571588957\"\u003e \n \u003cbr\u003e在图中我们对每个节点都有编号了。 8号节点是这棵树的根。我们定义,一个子节点向它的根节点的路径上,任意一个节点都称为它的祖先。例如, 4号节点是16号节点的祖先。而10号节点同样也是16号的祖先。事实上,16号的祖先有8,4,10,16共四个。另外8, 4, 6,7都是7号节点的祖先,所以7号和16号的公共祖先是4和8号,而在这两个里面,4号是距离7和16最近的一个,所以我们称7号和16号的最近公共祖先是4号。\n \u003cbr\u003e \n \u003cbr\u003e再例如,2和3的最近公共祖先是10,再例如6和13的是8。\n \u003cbr\u003e \n \u003cbr\u003e现在你需要编写一个程序,在一棵树中找出指定两个节点的最近公共祖先 \n \u003cbr\u003e \n \u003cbr\u003e\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 第一行输入T表示有T组数据。每组第一行是N表示这棵树有多少个节点,其中 2\u0026lt;\u003dN\u0026lt;\u003d10,000。 节点用正整数1, 2,..., N表示。 接下来的 N -1 行表示这棵树的边,每行两个数,都是节点编号,前一个是后一个的父节点。最后一行是要查询的两个节点,计算出这两个节点的最近公共祖先 \n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 对于每组测试输出一行,输出它们的最近公共祖先的编号。 \n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e2\n16\n1 14\n8 5\n10 16\n5 9\n4 6\n8 4\n4 10\n1 13\n6 15\n10 11\n6 7\n10 2\n16 3\n8 1\n16 12\n16 7\n5\n2 3\n3 4\n3 1\n1 5\n3 5\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e4\n3\n\n\u003c/pre\u003e"}}]}