DMOPC '18 Contest 3 P4 - Bob and English Class

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 2.0s
Java 5.0s
Memory limit: 256M
Java 256M

Author:
Problem types

Bob's English class has been given a project which must be done in pairs. The class size, 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 zones labelled 1, 2, \ldots, N. There are N-1 roads so that one can travel from any zone to any other. The i^{\text{th}} road connects zones a_i and b_i and has distance d_i.

The i^{\text{th}} student lives in zone 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} 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 is even
1\le z_i\le N
1\le a_i, b_i\le N
1\le d_i\le 1\ 000

Subtask 1 [10%]

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

Subtask 2 [20%]

2\le K\le 10
2\le N\le 200\ 000

Subtask 3 [30%]

2\le K\le 70
2\le N\le 70

Subtask 4 [40%]

2\le K\le 200\ 000
2\le N\le 200\ 000

Input Specification

The first line contains two space-separated integers, K and N.
The next line contains K space-separated integers, z_1, z_2, \ldots, z_K.
The next N-1 lines each contain three space-separated integers, a_i, b_i, d_i, the description of 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

7

Explanation for Sample 1

The pairs of students (1, 5), (2, 6), (3, 7), (4, 8) give costs 0, 0, 7, 0. The total is 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

36

Explanation for Sample 2

The pairs of students (1, 8), (2, 7), (3, 6), (4, 5) give costs 12, 13, 10, 1. The total is 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

20

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. The total is 20 which is the maximum possible.


Comments

There are no comments at the moment.