P4383 [Eight-Province Joint Exam 2018] Link-Cut Tree

Little L has recently become obsessed with The Legend of Zelda: Breath of the Wild, and he especially enjoys the mini challenges. In the game, there is a challenge called LCT. Its rules are as follows: There is a tree with $N$ nodes. Each edge has an integer weight $v_i$. If $v_i \geq 0$, traversing this edge yields a gain of $v_i$; if $v_i \lt 0$, traversing this edge requires paying a toll of $-v_i$. Little L needs to control the protagonist Link to cut exactly $K$ edges from the tree, then connect $K$ new edges each with weight $0$, producing a new tree. Next, he will choose two nodes $p, q$ on the tree, and walk from $p$ to $q$ along the unique simple path connecting them, paying tolls or obtaining gains for each edge he traverses. The god of Hyrule, TemporaryDO, wants to test Link. He tells Link that if Link can cut appropriate edges and choose an appropriate path so that the total gain $-$ total toll is maximized, he will give him the legendary Master Sword. Little L wants the Master Sword, so he asks you for help. Please tell him the maximum possible value of total gain $-$ total toll that Link can obtain.

The first line contains two positive integers $N, K$. The next $N - 1$ lines each contain three integers $x_i, y_i, v_i$, indicating that the $i$-th edge connects nodes $x_i$ and $y_i$, and its weight is $v_i$.

Output a single integer, the answer.

Sample Explanation: One possible optimal plan is: cut edge $(2, 4, -3)$, add edge $(3, 4, 0)$, and choose $(p, q) = (1, 5)$. Constraints: - For $10\%$ of the testdata, $K = 0$. - For another $10\%$ of the testdata, $K = 1$. - For another $15\%$ of the testdata, $K = 2$. - For another $25\%$ of the testdata, $K \leq 100$. - For the remaining testdata, there are no special constraints. For all testdata, it is guaranteed that $1 \leq N \leq 3 \times 10^5$, $0 \leq K \leq 3 \times 10^5$, $K \lt N$, $1 \leq x_i, y_i \leq N$, and $|v_i| \leq 10^6$. Hint: This problem is not difficult. Translated by ChatGPT 5