NOI '22 Multi-Provincial Team Selection P6 - MIS - Olympiads Online Judge

NOI '22 Multi-Provincial Team Selection P6 - MIS

View as PDF

Submit solution

All submissions

Best submissions

Points: 40 (partial)

Time limit: 1.0s

Memory limit: 1G

Problem type

Tommy has a binary tree rooted at $1$ $1$ on $n$ $n$ nodes. Each node has an integer weight $w_i$ $w_{i}$ , and the father of node $i = 2, 3, \dots, n$ $i = 2, 3, \dots, n$ is $f_i$ $f_{i}$ . Tommy needs to disassemble this binary tree by sequentially removing edges. When an edge $(u, v)$ $(u, v)$ is removed, the following happen, simultaneously:

$w_u+w_v$ $w_{u} + w_{v}$ units of cost are incurred;
$w_u$ $w_{u}$ and $w_v$ $w_{v}$ are swapped.

Find the minimum units of cost necessary to disassemble the binary tree.

Constraints

$2 \le n \le 5000$ $2 \leq n \leq 5000$

$1 \le w_i \le 10^9$ $1 \leq w_{i} \leq 10^{9}$

Test	$n \le$ $n \leq$
1 - 3	$10$ $10$
4 - 7	$100$ $100$
8 - 11	$500$ $500$
12 - 16	$1\,000$ $1 000$
17 - 25	$5\,000$ $5 000$

Input Specification

The first line contains a positive integer $n$ $n$ .

The second line contains $n$ $n$ positive integers $w_1, w_2, \dots, w_n$ $w_{1}, w_{2}, \dots, w_{n}$ .

The third line contains $n-1$ $n - 1$ positive integers $f_2, f_3, \dots, f_n$ $f_{2}, f_{3}, \dots, f_{n}$ , describing the binary tree.

Output Specification

Output the answer.

Sample Input 1

Copy

3
2 1 3
1 1