{"problem":{"name":"[NAPC-#1] rStage5 - Hard Conveyors","description":{"content":"**本题与 Stage5 的区别是合法路径定义不同**（简要题意中加粗部分不同）。~~（其实还有：样例不同，数据不同，部分分不同。）~~ ### 【简要题意】 给定一棵 $n$ 个节点的无根树以及树上的 $k$ 个关键节点，边有边权（即边的长度）。$q$ 次询问，每次给出 $s,t$，问从 $s$ 到 $t$ 且经过**至少一个**关键节点的路径的最短长度。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9432"},"statements":[{"statement_type":"Markdown","content":"**本题与 Stage5 的区别是合法路径定义不同**（简要题意中加粗部分不同）。~~（其实还有：样例不同，数据不同，部分分不同。）~~\n\n### 【简要题意】\n\n给定一棵 $n$ 个节点的无根树以及树上的 $k$ 个关键节点，边有边权（即边的长度）。$q$ 次询问，每次给出 $s,t$，问从 $s$ 到 $t$ 且经过**至少一个**关键节点的路径的最短长度。\n\n## Input\n\n第一行三个正整数 $n, q, k$，表示树的节点个数，询问次数和关键节点个数。\n\n接下来 $n-1$ 行，每行三个正整数 $u, v, w$，表示树中存在边 $(u, v)$，边权为 $w$。保证输入构成一棵树。\n\n接下来一行 $k$ 个两两不同的正整数，表示关键节点的编号。\n\n接下来 $q$ 行，每行两个正整数 $s, t$，表示一次询问。\n\n## Output\n\n对于每次询问输出一行一个非负整数，表示此次询问的最短合法路径长度。\n\n注意，合法路径可以不经过任何边，此时路径长为 $0$。\n\n[samples]\n\n## Background\n\n**本题新增两组 hack 数据。**\n\n---\n![](https://cdn.luogu.com.cn/upload/image_hosting/bp1ypbgf.png)\n\n更硬，所以可能就更脆，所以更容易被击破（确信）。\n\n您只花了两个小时就秒掉了正城 s1~s10，来秒逆城了。\n\n## Note\n\n### 【数据范围】\n\nupd at `2023-6-25`：新增了两组 hack 数据，将其置于 $\\text{Sub}\\textsf6$ 中，不记分数。\n\n**本题采用捆绑测试。**\n\n$$\n\\def\\r{\\cr\\hline}\n\\def\\None{\\text{None}}\n\\def\\arraystretch{1.5}\n\\begin{array}{c|c|c|c}\n\\textbf{Subtask} & \\text{测试点编号} & \\textbf{Sp. Constraints} & \\textbf{Score}\\r\n\\textsf1&1\\sim2 & k=n & 5 \\r\n\\textsf2&16\\sim20 &k=1,n\\leqslant10^3,q\\leqslant10^3 & 15 \\r\n\\textsf3&21\\sim25 & n\\leqslant10^3,q\\leqslant10^3 & 15 \\r\n\\textsf4&3\\sim7 & q=1 & 15 \\r\n\\textsf5&8\\sim15 & - & 50 \\r\n\\textsf6&26\\sim27 & - & 0 \\r\n\\end{array}\n$$\n\n对于 $100\\%$ 的数据，$1\\leqslant n\\leqslant 10^5$，$1\\leqslant q\\leqslant 10^5$，$1\\leqslant k\\leqslant n$，$1\\leqslant w\\leqslant 10^4$，$1\\leqslant u,v,s,t\\leqslant n$。\n\n### 【样例解释 #1】\n![](https://cdn.luogu.com.cn/upload/image_hosting/3hvr33bz.png)\n\n图中加粗节点表示关键点。\n\n对于每组询问，以下为一种最优路径（最优路径可能有多条）：\n1. $2\\to1\\to3$。\n2. $2\\to1$。\n3. $7\\to1\\to2\\to1$。\n4. $4\\to3\\to5$。\n5. $6\\to2\\to6$。\n6. $2$（合法路径可以不经过任何边，此时路径长为 $0$）。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9432","tags":["O2优化","最近公共祖先 LCA","树链剖分"],"sample_group":[["7 6 2\n1 2 3\n1 3 5\n3 4 2\n3 5 4\n2 6 1\n1 7 1\n2 3\n2 3\n2 1\n7 1\n4 5\n6 6\n2 2","8\n3\n7\n6\n2\n0"]],"created_at":"2026-03-03 11:09:25"}}