P10641 BZOJ3252 Walkthrough.

As everyone knows, Katsuragi Keima is the god of “walkthroughs”. After turning on god mode, he can play through $k$ games at the same time. Today he got a new game called *XX Peninsula*. This game has $n$ scenes. From some scenes, you can reach other scenes through different choices. All scenes and choice branches form a tree structure: when the game starts, you are at the root node (common route), and the leaf nodes are endings. Each scene has a value. Now Keima turns on god mode and plays through this game $k$ times at the same time. What is the maximum possible total value of the scenes he gets to watch? (Watching the same scene multiple times does not give the value repeatedly.) > “Why do you already know the value of each scene before playing?” > “I have already seen the ending.”

Given a tree with $n$ nodes. Each node has a positive integer weight. Select $k$ simple paths that start from the root node and end at leaf nodes. Find the maximum possible sum of the weights of all nodes in the union of these paths.

The first line contains two positive integers $n, k$. The second line contains $n$ positive integers $w_i$, representing the weight of each node. Then follow $n - 1$ lines. Each line contains two positive integers $u, v$, meaning node $u$ is the parent of node $v$.

Output one positive integer, the answer.

For all testdata, it is guaranteed that $1 \leq n \leq 2 \times 10^5$, and $1 \leq w_i \leq 2^{31} - 1$. Translated by ChatGPT 5