DMOPC '18 Contest 3 P4 - Bob and English Class

Points: 15 (partial)

Time limit: 1.0s

Java 2.5s

Memory limit: 256M

Author:

Problem types

Bob's English class has been given a project which must be done in pairs. The class size, $K$ ~K~, is even. Each pair needs to meet outside class to do the project.

The city which Bob and his classmates live in is a tree. It has $N$ ~N~ zones labelled $1, 2, \dots, N$ ~1, 2, \dots, N~. There are $N-1$ ~N-1~ roads so that one can travel from any zone to any other. The $i^\text{th}$ ~i^\text{th}~ road connects zones $a_i$ ~a_i~ and $b_i$ ~b_i~ and has distance $d_i$ ~d_i~.

The $i^\text{th}$ ~i^\text{th}~ student lives in zone $z_i$ ~z_i~. Bob defines the cost of a pair to be the distance between the zones of the two students in the pair. Bob is wondering what the total of the $\frac{K}{2}$ ~\frac{K}{2}~ costs is. Since the pairs haven't been assigned yet, he wants to know the worst-case. That is, what is the maximum possible total of the costs?

Constraints

$K$ ~K~ is even
$1 \le z_i \le N$ ~1 \le z_i \le N~
$1 \le a_i, b_i \le N$ ~1 \le a_i, b_i \le N~
$1 \le d_i \le 1\,000$ ~1 \le d_i \le 1\,000~

Subtask 1 [10%]

$a_i=i, b_i=i+1$ ~a_i=i, b_i=i+1~ for all $i=1, 2, \dots, N-1$ ~i=1, 2, \dots, N-1~
$2 \le K \le 200\,000$ ~2 \le K \le 200\,000~
$2 \le N \le 200\,000$ ~2 \le N \le 200\,000~

Subtask 2 [20%]

$2 \le K \le 10$ ~2 \le K \le 10~
$2 \le N \le 200\,000$ ~2 \le N \le 200\,000~

Subtask 3 [30%]

$2 \le K \le 70$ ~2 \le K \le 70~
$2 \le N \le 70$ ~2 \le N \le 70~

Subtask 4 [40%]

$2 \le K \le 200\,000$ ~2 \le K \le 200\,000~
$2 \le N \le 200\,000$ ~2 \le N \le 200\,000~

Input Specification

The first line contains two space-separated integers, $K$ ~K~ and $N$ ~N~.
The next line contains $K$ ~K~ space-separated integers, $z_1, z_2, \dots, z_K$ ~z_1, z_2, \dots, z_K~.
The next $N-1$ ~N-1~ lines each contain three space-separated integers, $a_i, b_i, d_i$ ~a_i, b_i, d_i~, the description of $i^\text{th}$ ~i^\text{th}~ road.

Output Specification

Output a single integer, the maximum possible total.

Sample Input 1

8 4
2 2 2 2 1 2 2 2
1 2 7
1 3 3
1 4 1

Sample Output 1

Explanation for Sample 1

The pairs of students $(1, 5), (2, 6), (3, 7), (4, 8)$ ~(1, 5), (2, 6), (3, 7), (4, 8)~ give costs $0, 0, 7, 0$ ~0, 0, 7, 0~. The total is $7$ ~7~ which is the maximum possible.

Sample Input 2

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

Sample Output 2

Explanation for Sample 2

The pairs of students $(1, 8), (2, 7), (3, 6), (4, 5)$ ~(1, 8), (2, 7), (3, 6), (4, 5)~ give costs $12, 13, 10, 1$ ~12, 13, 10, 1~. The total is $36$ ~36~ which is the maximum possible.

Sample Input 3

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

Sample Output 3

Explanation for Sample 3

The pairs of students $(1, 6), (2, 7), (3, 8), (4, 9), (5, 10)$ give costs $4, 4, 4, 4, 4$ ~4, 4, 4, 4, 4~. The total is $20$ ~20~ which is the maximum possible.

Comments

There are no comments at the moment.