有根树拓扑序最小逆序对

【题目描述】

给定：

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

树的根是顶点 $0$，顶点 $i$ 的父亲是 $p_i$。

求一个 $(0,1,\dots,N-1)$ 的排列 $p$，满足以下条件。若有多组合法的答案，你可以任选一组。

• 若 $i\neq j$ 且顶点 $p_i$ 是顶点 $p_j$ 的祖先，则必须满足 $i \lt j$。
• 在满足上述条件的所有方案中，值 $X=\sum_{i=0}^{N-1}\sum_{j=0}^{i-1} c_{p_i} d_{p_j}$ 最小。

输出 $X$ 的最小值，以及一组使 $X$ 取到该最小值的排列 $p$。

【输入】

$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$ $\ldots$ $p_{N-1}$

【输入样例】

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

【输入样例2】

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

【输出样例2】

10000000400000005
0 1 2 4 3

【数据范围】

• $1 \leq N \leq 200000$
• $0 \leq p_i \lt i$
• $0 \leq c_i \leq 1000000000$
• $0 \leq d_i \leq 1000000000$
• $\sum_{i=0}^{N-1} c_i \leq 1000000000$
• $\sum_{i=0}^{N-1} d_i \leq 1000000000$

【来源】

Library Checker（yosupo06） rooted_tree_topological_order_with_minimum_inversions

本题为 special judge（输出任意合法解），暂不可本地评测。