{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv id\u003d\"problem-body\"\u003e \n \u003cp\u003e给定一个包含 \u003cstrong\u003eN\u003c/strong\u003e 个结点的树. 树节点从 \u003cstrong\u003e1\u003c/strong\u003e 到 \u003cstrong\u003eN\u003c/strong\u003e编号.。每个节点有一个整数权值。\u003c/p\u003e \n \u003cp\u003e我们会要求您执行以下操作:\u003c/p\u003e \n \u003cul\u003e \n \u003cli\u003e\u003cstrong\u003eu v k\u003c/strong\u003e : 询问从节点 \u003cstrong\u003eu\u003c/strong\u003e 到 节点 \u003cstrong\u003ev\u003c/strong\u003e 的路径上的第k小的权值\n \u003ch3\u003e输入\u003c/h3\u003e \n \u003cp\u003e在第一行中有两个整数\u003cstrong\u003eN\u003c/strong\u003e 和 \u003cstrong\u003eM\u003c/strong\u003e(\u003cstrong\u003eN, M\u003c/strong\u003e \u0026lt;\u003d 100000)\u003c/p\u003e \n \u003cp\u003e在第二行中有\u003cstrong\u003eN\u003c/strong\u003e 个整数, 第i个整数表示第i个节点的权值。\u003c/p\u003e \n \u003cp\u003e接下来的\u003cstrong\u003eN-1\u003c/strong\u003e 行, 每行包含两个整数 \u003cstrong\u003eu\u003c/strong\u003e \u003cstrong\u003ev\u003c/strong\u003e, 它表示有一条边 (\u003cstrong\u003eu\u003c/strong\u003e, \u003cstrong\u003ev\u003c/strong\u003e).\u003c/p\u003e \n \u003cp\u003e在接下来的 \u003cstrong\u003eM\u003c/strong\u003e 行中, 每行有三个整数 \u003cstrong\u003eu\u003c/strong\u003e \u003cstrong\u003ev\u003c/strong\u003e \u003cstrong\u003ek\u003c/strong\u003e, 代表查询从节点 \u003cstrong\u003eu\u003c/strong\u003e 到节点 \u003cstrong\u003ev\u003c/strong\u003e的路径上权值第k小的节点的权值。\u003c/p\u003e \n \u003ch3\u003e输出\u003c/h3\u003e \n \u003cp\u003e对于每个操作,输出其结果。\u003c/p\u003e \n \u003ch3\u003e样例\u003c/h3\u003e \n \u003cpre\u003e\u003cstrong\u003e样例输入:\u003c/strong\u003e\n8 5\n105 2 9 3 8 5 7 7\n1 2\n1 3\n1 4\n3 5\n3 6\n3 7\n4 8\u003cbr\u003e2 5 1\u003cbr\u003e2 5 2\u003cbr\u003e2 5 3\u003cbr\u003e2 5 4\u003cbr\u003e7 8 2\u0026nbsp;\u003c/pre\u003e \n \u003cpre\u003e\u003cstrong\u003e样例输出:\u003c/strong\u003e\n2\u003cbr\u003e8\u003cbr\u003e9\u003cbr\u003e105\u003cbr\u003e7\u0026nbsp;\u003c/pre\u003e \n \u003c/div\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}}]}