Minimizing Discomfort in Dragon’s Feast

A nine‐headed dragon with \(M\) heads finds a fruit tree with \(N\) fruits, and each fruit is connected by \(N-1\) branches forming a tree. Each branch has a nonnegative discomfort value when eaten. The dragon must divide the \(N\) fruits into \(M\) groups (each group containing at least one fruit) so that each head gets one group.

Among the \(M\) heads one is the largest (called the big head) and must eat exactly \(K\) fruits. Moreover, by common sense the group for the big head must include the unique largest fruit. When two fruits connected by a branch are eaten by the same head, that head lazily eats the branch along with the fruits (incurring its discomfort value). If the two fruits are eaten by different heads, the branch is broken (and no discomfort is incurred from that branch).

The overall discomfort value of the dragon is defined as the sum of the discomfort values of all branches that are eaten (i.e. the branches not broken). The dragon wants to minimize this total discomfort value. Your task is to help compute the minimum total discomfort value.

Note: It is equivalent to partition the tree by cutting some branches. Every branch that is cut yields no discomfort, while every uncut branch is eaten and adds its discomfort value to the total. Since the sum of all branch discomfort values is constant, minimizing eaten discomfort is equivalent to maximizing the total discomfort value of the branches cut. With a proper choice of cuts, the fruits can be partitioned into \(M\) groups. In particular, if we let \(X\) be the connected component containing the largest fruit (i.e. the big head’s group), we require that \(|X| = K\) and the number of cut edges on the boundary of \(X\) is \(M-1\) (since the complement will form exactly \(M-1\) connected components).

Input Format: The first line contains three integers \(N, M, K\) (\(1 \le K \le N\)). The second line contains \(N\) positive integers representing the values of the fruits. It is guaranteed that the largest fruit is unique. Each of the next \(N-1\) lines contains three integers \(u, v, w\), indicating that there is an edge between fruits \(u\) and \(v\) with discomfort value \(w\) (\(w \ge 0\)). The fruits are numbered from 1 to \(N\).

Output Format: Output one integer which is the minimum total discomfort value. If there is no valid partition satisfying the conditions, output -1.

Explanation: Let \(W_{total}\) be the sum of all branches' discomfort values. If the maximum total discomfort value of the branches cut (subject to forming a connected subgraph \(X\) of size \(K\) that contains the largest fruit and having exactly \(M-1\) cut edges) is \(W_{cut}\), then the answer is \(W_{total} - W_{cut}\).

inputFormat

The first line contains three integers \(N\), \(M\) and \(K\) (the number of fruits, the number of heads, and the number of fruits the big head must eat, respectively).
The second line contains \(N\) positive integers: the value of each fruit. It is guaranteed that the maximum fruit value is unique.
Each of the following \(N-1\) lines contains three integers \(u\), \(v\) and \(w\), describing an undirected edge between fruits \(u\) and \(v\) with discomfort value \(w\).

outputFormat

Output one integer — the minimum total discomfort value the dragon must endure. If no valid partition exists, output -1.

sample

8 2 4
5 3 10 2 1 4 6 7
3 1 3
3 2 2
3 4 4
4 5 1
4 6 5
3 7 2
7 8 3

13