P10070 [CCO 2023] Travelling Trader

一个商人想要在城市之间做生意，把货物从一个城市运到另一个城市来获得利润。有 $N$ 个城市，用 $1, \ldots, N$ 表示。有 $N-1$ 条道路，每条道路连接两个城市，每条道路需要一天的时间来穿越。使用这些道路，可以从任何一个城市到达另一个城市。 如果商人当前在第 $i$ 个城市并选择做生意，那么商人可以获得 $p_{i}$ 的利润，但是对于每个城市这个利润只能获得一次。商人从第 $1$ 个城市开始做生意，沿着道路访问城市，以最大化他们的总利润。但是如果商人太久没有获得利润，商人的老板会变得不高兴。具体地说，一旦商人连续超过 K 天没有获得利润，老板就会解雇商人。注意：无论商人是否在其中一个城市做生意，商人在相邻的城市之间移动都需要一天的时间。你需要求出商人可以获得的最大利润和能够获得这个利润的路线。 求出商人能得到的可能的最大总利润，并构造一种方案。

无

无

**样例解释 1** 在第 $1$ 天，商人从第 $1$ 个城市开始做生意，获得 $3$ 的利润。 在第 $2$ 天，商人移动到第 $3$ 个城市，并在那里做生意，获得 $4$ 的利润。 在第 $3$ 天，商人无法在被解雇之前到达另一个他们没有做过生意的城市，所以他们的总利润是 $7$。 **样例解释 2** 商人按照 $1,2,4,2,5,2,1,3$ 的顺序访问它们，可以在每个城市获得利润。 注意，商人为了确保他们不会超过 $2$ 天没有获得利润，推迟了在第 $2$ 个城市做生意的时间。 对于所有数据，有 $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$ 的范围 |$K$ 的范围| |:-:|:-:|:-:|:-:| |1 |8 |$2 \leq N \leq 2\times 10^5$| $K=1$| |2 |28 |$2 \leq N \leq 200$| $K=2$| |3 |12 |$2 \leq N \leq 2000$|$K=2$| |4 |16 |$2 \leq N \leq 2\times 10^5$|$K=2$| |5 |16 |$2 \leq N \leq 2000$| $K=3$| |6 | 20 | $2 \leq N \leq 2\times 10^5$|$K=3$|