P10610 Gate to Another World

Following the clues, Renko arrived at Tanabatazaka. With no time to admire the scenery, her mind raced as she searched for traces of another world. Flipped Jizō statues, strange fissures, a hidden fifth season... This forbidden realm was revealing its secrets to her. But the first thing Renko saw was Merry. Without hesitation, she grabbed Merry's hand—

With keen intuition, Renko realized the method to enter this otherworld must be linked to these special Jizō statues. She discovered they formed a uniquely structured tree. Given a **rooted** tree with $n$ nodes, where the root is node $1$, and each node $i$ has a weight $w_i$. **For any two nodes at the same depth, they have the same number of children.** To enter the otherworld, Renko performed operations to modify the tree's node weights: 1. Select an edge connecting nodes $(u,v)$, where $u$ is the deeper node (i.e., $u$ is $v$'s child). Add $w_v$ to $w_u$. 2. This operation can be performed any number of times, but **the same edge cannot be selected more than once**. After these operations, Renko derived a [DFS sequence](https://oi-wiki.org/graph/dfs/) of the tree and recorded the corresponding weight sequence $c$ (specifically, $c_i$ is the weight of the $i$-th node visited in the DFS order). Unfortunately, she forgot which operations she performed and how the DFS was conducted. Your task is to reconstruct any valid set of operations and DFS sequence.

- The first line contains an integer $n$. - The next $n$ lines each contain two integers $f_i$ and $w_i$: - $f_i$ is the parent of node $i$ (note: $f_1=0$, and for other nodes, $1 \leq f_i < i$). - $w_i$ is the initial weight of node $i$. - The next line contains $n$ integers describing the target weight sequence $c$. It is guaranteed that there exists a valid set of operations and DFS order to achieve $c$.

- The first line contains an integer $m$, the number of operations performed. - The second line contains $m$ integers $x_1, x_2, \ldots, x_m$, where $x_i$ represents the edge between node $x_i$ and its parent $f_{x_i}$ chosen in the $i$-th operation. - The third line contains a permutation $p$ of $n$ integers, where $p_i$ is the $i$-th node visited in your constructed DFS sequence.

### Sample Explanations #### Sample #1 One valid solution is to operate edges $(2,3)$, $(3,4)$, $(1,2)$ in order. The final weights are $\{1,3,5,9\}$, and the DFS sequence is $1,2,3,4$. This sample satisfies **Special Property A**. #### Sample #2 One valid solution is to operate edges $(1,2)$, $(3,5)$, $(1,3)$. The final weights are $\{1,0,0,3,3\}$, and the DFS sequence is $1,2,4,3,5$. #### Sample #3 One valid solution is to operate edge $(1,2)$. The final weights are $\{1,3,3,4\}$, and the DFS sequence is $1,4,2,3$. This sample satisfies **Special Property B**. #### Sample #4 One valid solution is to operate edges $(1,2)$, $(2,4)$, $(3,5)$, $(1,3)$. The final weights are $\{1,2,3,2,2\}$, and the DFS sequence is $1,3,5,2,4$. This sample satisfies **Special Property C**. ### Constraints **Bundled testing is used.** $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{Points} & \bm{n \leq} & \textbf{Special Property} & \textbf{Subtask Dependencies} \cr\hline 1 & 10 & 6 & - & - \cr\hline 2 & 10 & 100 & \mathbf{A} & - \cr\hline 3 & 10 & 100 & \mathbf{B} & - \cr\hline 4 & 15 & 2 \times 10^3 & \mathbf{C} & - \cr\hline 5 & 15 & 2 \times 10^3 & \mathbf{D} & - \cr\hline 6 & 15 & 100 & - & 1,2,3 \cr\hline 7 & 25 & 2 \times 10^3 & - & 1,2,3,4,5,6 \cr\hline \end{array} $$ **Special Properties**: - **A**: The tree satisfies $f_i = i-1$ for $i \neq 1$. - **B**: The tree satisfies $f_i = 1$ for $i \neq 1$. - **C**: All nodes have $w_i = 1$. - **D**: All non-leaf nodes have at most 2 children. For all data: $1 \leq n \leq 2000$, $-10^8 \leq w_i \leq 10^8$, $-10^{14} \leq c_i \leq 10^{14}$. --- Translated by DeepSeek R1