{"trustable":false,"sections":[{"title":"题目描述","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cp\u003e$LCA$ ($Lowest\\ Common\\ Ancestors$),即最近公共祖先,是指在有根树中,找出某两个节点 $u$ 和 $v$ 最近的公共祖先。(若 $u$ 为 $v$ 的祖先或者 $v$ 为 $u$ 的祖先,则 $LCA(u,v)$ 就是作为祖先的那个节点)。\u003c/p\u003e \n \u003cp\u003e现在有一棵以 $1$ 为根的有根树,树上一共有 $n$ 个节点。现在有 $m$ 次查询,每次询问两个节点的 $LCA$。\u003c/p\u003e \n \u003cp style\u003d\"text-align:center\"\u003e\u003cimg alt\u003d\"\" height\u003d\"330\" src\u003d\"CDN_BASE_URL/3b0110db28a493f25f1f91d133e5faaf?v\u003d1656056243\" width\u003d\"329\"\u003e\u003c/p\u003e \n \u003cp\u003e如图所示的数据中,$LCA(3,5)\u003d1,LCA(2,5)\u003d2,LCA(3,4)\u003d1,LCA(2,4)\u003d2,LCA(5,5)\u003d5$。\u003c/p\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n 第1行:一个正整数n,表示树上节点的个数。(1\u0026lt;\u003dn\u0026lt;\u003d1000) 第2行-第n行:每行两个正整数u,v,表示节点u到节点v有一条边。(1\u0026lt;\u003du,v\u0026lt;\u003dn) 第n+1行:一个正整数m,表示查询的次数。(1\u0026lt;\u003dm\u0026lt;\u003d1000) 第n+2-第n+m+1行:每行两个正整数a,b,表示要查询的两个节点的编号。(1\u0026lt;\u003da,b\u0026lt;\u003dn)\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n 对于每个询问,输出一个正整数表示答案,并换行。\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1 2\n1 3\n2 4\n2 5\n5\n3 5\n2 5\n3 4\n2 4\n5 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n1\n2\n5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}