{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027],[\u0027\\[\u0027,\u0027\\]\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027description-container\u0027]);}, 2000);\u003c/script\u003e\n\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cp\u003eLCA(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\u003d1589893236\" 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 Input","value":{"format":"HTML","content":"\u003cpre\u003e5\n1 2\n1 3\n2 4\n2 5\n5\n3 5\n2 5\n3 4\n2 4\n5 5\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e1\n2\n1\n2\n5\u003c/pre\u003e"}}]}