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^{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^{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 \leq z_{i} \leq N$
$1 \le a_i, b_i \le N$ $1 \leq a_{i}, b_{i} \leq N$
$1 \le d_i \le 1\,000$ $1 \leq d_{i} \leq 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 \leq K \leq 200 000$
$2 \le N \le 200\,000$ $2 \leq N \leq 200 000$

Subtask 2 [20%]

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

Subtask 3 [30%]

$2 \le K \le 70$ $2 \leq K \leq 70$
$2 \le N \le 70$ $2 \leq N \leq 70$

Subtask 4 [40%]

$2 \le K \le 200\,000$ $2 \leq K \leq 200 000$
$2 \le N \le 200\,000$ $2 \leq N \leq 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^{th}$ road.

Output Specification

Output a single integer, the maximum possible total.

Sample Input 1

Copy

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

Sample Output 1

Copy

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

Copy

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

Copy

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

Copy

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

Copy

Explanation for Sample 3

The pairs of students $(1, 6), (2, 7), (3, 8), (4, 9), (5, 10)$ $(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.