{"problem":{"name":"[CCO 2023] Travelling Trader","description":{"content":"一个商人想要在城市之间做生意，把货物从一个城市运到另一个城市来获得利润。有 $N$ 个城市，用 $1, \\ldots, N$ 表示。有 $N-1$ 条道路，每条道路连接两个城市，每条道路需要一天的时间来穿越。使用这些道路，可以从任何一个城市到达另一个城市。 如果商人当前在第 $i$ 个城市并选择做生意，那么商人可以获得 $p_{i}$ 的利润，但是对于每个城市这个利润只能获得一次。商人从第 $1","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10070"},"statements":[{"statement_type":"Markdown","content":"一个商人想要在城市之间做生意，把货物从一个城市运到另一个城市来获得利润。有 $N$ 个城市，用 $1, \\ldots, N$ 表示。有 $N-1$ 条道路，每条道路连接两个城市，每条道路需要一天的时间来穿越。使用这些道路，可以从任何一个城市到达另一个城市。\n\n如果商人当前在第 $i$ 个城市并选择做生意，那么商人可以获得 $p_{i}$ 的利润，但是对于每个城市这个利润只能获得一次。商人从第 $1$ 个城市开始做生意，沿着道路访问城市，以最大化他们的总利润。但是如果商人太久没有获得利润，商人的老板会变得不高兴。具体地说，一旦商人连续超过 K 天没有获得利润，老板就会解雇商人。注意：无论商人是否在其中一个城市做生意，商人在相邻的城市之间移动都需要一天的时间。你需要求出商人可以获得的最大利润和能够获得这个利润的路线。\n\n求出商人能得到的可能的最大总利润，并构造一种方案。\n\n## Input\n\n第一行包含两个用空格分隔的整数 $N$ 和 $K$。\n\n接下来的 $N-1$ 行，每行包含两个用空格分隔的整数 $u_{i}$ 和 $v_{i}$，表示一条道路。\n\n最后一行包含 $N$ 个整数 $p_{1}, \\ldots, p_{N}$，表示选择在相应的城市做生意所给的利润。\n\n## Output\n\n第一行输出一个整数，表示可能的最大总利润。\n\n第二行输出一个整数 $M\\ (1 \\leq M \\leq N)$，表示在最优路线上商人做生意的城市的数量。\n\n第三行，输出 $M$ 个用空格分隔的整数 $x_{1}, \\ldots, x_{M}$，表示商人按顺序在最优路线上做生意的城市，从 $x_1=1$ 开始。\n\n如果有多个正确方案，你可以输出任何一个。\n\n[samples]\n\n## Note\n\n**样例解释 1**\n\n在第 $1$ 天，商人从第 $1$ 个城市开始做生意，获得 $3$ 的利润。\n\n在第 $2$ 天，商人移动到第 $3$ 个城市，并在那里做生意，获得 $4$ 的利润。\n\n在第 $3$ 天，商人无法在被解雇之前到达另一个他们没有做过生意的城市，所以他们的总利润是 $7$。\n\n**样例解释 2**\n\n商人按照 $1,2,4,2,5,2,1,3$ 的顺序访问它们，可以在每个城市获得利润。\n\n注意，商人为了确保他们不会超过 $2$ 天没有获得利润，推迟了在第 $2$ 个城市做生意的时间。\n\n对于所有数据，有 $2 \\leq N \\leq 2\\times 10^5，1\\leq K\\le 3，1 \\leq u_{i}, v_{i} \\leq N，u_{i} \\neq v_{i}，1 \\leq p_{i} \\leq 10^{9}$。\n\n|子任务编号\t|分值|\t$N$ 的范围\t|$K$ 的范围|\n|:-:|:-:|:-:|:-:|\n|1\t|8\t|$2 \\leq N \\leq 2\\times 10^5$|\t$K=1$|\n|2\t|28\t|$2 \\leq N \\leq 200$|\t$K=2$|\n|3\t|12\t|$2 \\leq N \\leq 2000$|$K=2$|\n|4\t|16\t|$2 \\leq N \\leq 2\\times 10^5$|$K=2$|\n|5\t|16\t|$2 \\leq N \\leq 2000$|\t$K=3$|\n|6 | 20 | $2 \\leq N \\leq 2\\times 10^5$|$K=3$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10070","tags":["2023","Special Judge","CCO（加拿大）"],"sample_group":[["4 1\n1 2\n1 3\n2 4\n3 1 4 1","7\n2\n1 3"],["5 2\n1 2\n1 3\n2 4\n2 5\n3 1 4 1 5","14\n5\n1 4 5 2 3"]],"created_at":"2026-03-03 11:09:25"}}