역전 수가 최소인 루트 있는 트리의 위상 순서

다음이 주어진다.

• $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$을 출력한다.

제약 조건

• $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$

$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}$