根树拓扑序最小逆序值（Rooted Tree Topological Order with Minimum Inversions）

题目描述

给定：

• 一棵含 $N$ 个顶点的有根树，根为顶点 $0$；
• $N$ 个整数 $c_0, c_1, \dots, c_{N-1}$；
• $N$ 个整数 $d_0, d_1, \dots, d_{N-1}$。

对于顶点 $i$（$i \ge 1$），其父节点为 $p_i$，且保证 $0 \le p_i < i$。

求一个排列 $p = (p_0, p_1, \dots, p_{N-1})$，它是 $\{0, 1, \dots, N-1\}$ 的一个重排，并满足：

• 若 $i \ne j$ 且顶点 $p_i$ 是顶点 $p_j$ 的祖先，则 $i < j$。

在所有满足上述条件的排列中，使下式最小化：

$$X = \sum_{i=0}^{N-1} \sum_{j=0}^{i-1} c_{p_i} \cdot d_{p_j}$$

输出最小值 $X$，以及任意一个达到该最小值的排列 $p$。

约束条件

• $1 \le N \le 2 \times 10^5$
• 对于 $i = 1, 2, \dots, N-1$，有 $0 \le p_i < i$
• $0 \le c_i, d_i \le 10^9$
• $\sum_{i=0}^{N-1} c_i \le 10^9$
• $\sum_{i=0}^{N-1} d_i \le 10^9$

输入格式

N
p_1 p_2 ... p_{N-1}
c_0 c_1 ... c_{N-1}
d_0 d_1 ... d_{N-1}

输出格式

X
p_0 p_1 ... p_{N-1}

其中：

• $X$ 为最小化的值，
• $p_0, p_1, \dots, p_{N-1}$ 为达到 $X$ 的一个合法拓扑序。

10
0 0 0 1 2 2 4 7 8
41 10 46 7 30 4 30 12 48 32
47 38 25 31 37 48 16 17 34 13

29047
0 2 6 1 4 7 8 9 3 5

5
0 0 1 2
1 100000000 1 1 100000000
1 1 100000000 100000000 1

10000000400000005
0 1 2 4 3