Background

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.”

Problem Description

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.

Input Format

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 Format

Output one positive integer, the answer.

5 2
4 3 2 1 1
1 2
1 5
2 3
2 4

10

Hint

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