{"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":"MD","content":"一棵树有 n 个结点,树边有权值。需要进行以下操作:\n\n- **DIST a b** : 询问点 a 到点 b 路径上的权值和\n- **KTH a b k** : 询问点 a 到点 b 路径上的第 k 个点\n\n比如样例中,点 4 到点 6 的路径为 4 -\u003e 2 -\u003e 1 -\u003e 3 -\u003e 6 \n**DIST 4 6** : 答案是 5 (1 + 1 + 1 + 2 \u003d 5) \n**KTH 4 6 4** : 答案是 3 (路径上的第 k 个点是 3)\n\n### 输入格式\n\n第一行一个整数 t (1 \u003c\u003d t \u003c\u003d 25),表示数据组数。\n\n对每组测试数据: \n第一行一个整数 n (1 \u003c\u003d n \u003c\u003d 10000) \n接下来 n-1 行,每行三个整数 a,b,c 表示点 a 与点 b 之间有一条权值为c 的边 (1 \u003c\u003d a,b \u003c\u003d n , 1\u003c\u003d c \u003c\u003d 100000) \n接下来若干行为指令 `DIST a b` 或 `KTH a b k`。 \n每组测试数据以 `DONE` 结束。\n\n每组测试数据间有一个空行。\n\n### 输出格式\n\n对每个 `DIST` 或 `KTH` 指令,输出一个整数表示其答案。\n\n每组测试数据后输出一空行。\n\n### 样例输入\n```\n1\n\n6\n1 2 1\n2 4 1\n2 5 2\n1 3 1\n3 6 2\nDIST 4 6\nKTH 4 6 4\nDONE\n```\n\n### 样例输出\n```\n5\n3\n```\n"}}]}