P16066 [CSPro 32] Tree Search.

Luogu’s testdata are for community communication only and are not official testdata. Official judging link: 。

The Big Data Center on Xixi Aifu Island has launched a voluntary data contribution system in order to collect data for model training. Residents on the island can log in to the system and answer questions asked by the system, thus providing data for the Big Data Center. To ensure data quality, the system evaluates whether an answer is correct. If the answer is correct, the system gives a certain reward. Recently, the Big Data Center needs to collect a batch of data about noun classification. The system will preset several noun categories, and these categories have a hierarchical relationship. For example, “Animals” is a subcategory of “Living Things”, “Fish” is a subcategory of “Animals”, “Birds” is a subcategory of “Animals”, and “Fish” and “Birds” are sibling categories under “Animals”. These categories can be organized as a tree: except for the root category, each category has exactly one parent category. Also, every noun can be classified into some category, i.e., each noun corresponds to exactly one category. The descendant categories of a category are defined as follows: if the category has no subcategories, then it has no descendant categories; otherwise, its descendant categories are all its subcategories and all descendants of its subcategories. The following figure illustrates the subcategories and descendant categories of the category marked with an asterisk. :::align{center}  ::: The system asks users questions in the form: whether a noun belongs to a category, and the user can answer “Yes” or “No”. The meaning of the question is: whether the noun can be classified into that category or any of its descendant categories. For example, to determine the category of the noun “Cod”, the system may ask “Does cod belong to Animals?”. When the user answers “Yes”, the system further asks “Does cod belong to Fish?”. When the user answers “Yes”, it can determine that “Cod” can be classified into the “Fish” category. Also, if there is no more specific classification, a noun can be classified into a non-leaf category. For example, to determine the category of “Cat”, the system may ask “Does cat belong to Animals?”. When the user answers “Yes”, the system then asks separately whether “Cat” belongs to “Fish” and “Birds”. After both questions receive “No”, the system determines that “Cat” belongs to the “Animals” category. Based on previous experience, the Big Data Center already knows the likelihood that a noun belongs to each category. In order to determine a noun’s category with as few questions as possible, the Big Data Center hopes that Xiao C can design a method to reduce the number of questions asked to the user. Xiao C observed and analyzed the collected data and obtained information about the likelihood that a noun belongs to each category. Specifically, each category is assigned a value called a weight. The larger the value, the more likely a noun belongs to that category. Since each question can get one of two answers, Xiao C thought of a binary-search-like strategy. His strategy is as follows: 1. For each category, compute the sum of weights of this category and all of its descendant categories, and also compute the sum of weights of all remaining categories; take the absolute difference of these two sums, denoted as $w_\delta$。 2. Choose the category with the smallest $w_\delta$; if there are multiple, choose the one with the smallest index, and ask the user whether the noun belongs to this category. 3. If the user answers “Yes”, keep only this category and its descendant categories; otherwise, keep only the remaining categories. 4. Repeat step 1 until only one category remains; then the noun’s category is determined. Xiao C asks you to help write a program to test the effectiveness of this strategy. Your program first reads all categories, their parent-child relationships, and the weight of each category. Your program needs to test, for nouns classified into the given categories, all questions that will be asked to the user according to the strategy above.

Read data from standard input. The first line contains two space-separated positive integers $n$ and $m$, representing the total number of categories and the number of categories to be tested. All categories are numbered from $1$ to $n$, where category $1$ is the root category. The second line contains $n$ space-separated positive integers $w_1, w_2, \ldots, w_n$, where $w_i$ denotes the weight of category $i$. The third line contains $(n - 1)$ space-separated positive integers $p_2, p_3, \ldots, p_n$, where $p_{i+1}$ denotes the index of the parent category of category $(i + 1)$, and $p_i \in [1, n]$。 Then follow $m$ lines, each containing one positive integer, indicating the index of a category to be tested.

Output $m$ lines, each describing the test result for one tested category, i.e., the sequence of questions that will be asked, in order, for a noun that belongs to the given tested category under Xiao C’s questioning strategy. Each line contains several space-separated positive integers. Each integer is the index of the category appearing in one question, output in the order of questioning.

### Sample 1 Explanation The category relationship represented by the input data is shown in the figure below, and the weight of each category is also labeled in the figure. :::align{center}  ::: For a noun classified into category $5$, according to the strategy above, we should compute the value of $w_\delta$ for every node in the tree. For categories $1$ to $5$, the resulting $w_\delta$ values are $100$, $0$, $20$, $80$, $60$, respectively. Therefore, we first ask about category $2$. Since category $5$ is not in the descendant categories of category $2$, the user answers “No”. We then remove category $2$ and all of its descendant categories, keeping only categories $1$, $3$, $4$, and $5$. For the remaining categories, we compute $w_\delta$ again and obtain $50$, $30$, $30$, $10$, respectively. Therefore, we next ask about category $5$. Since category $5$ is exactly the noun’s category, the user answers “Yes”, and we keep only category $5$ and all of its descendant categories. We find that only category $5$ remains, so the algorithm ends. The process is shown below: :::align{center}  ::: For a noun classified into category $3$, according to the strategy above, we ask about categories $2$ and $5$ in order, and the process is the same as above. However, since category $3$ is not in the descendant categories of category $2$, the user answers “No”. At this time, we should remove category $5$ and its descendant categories, keeping only categories $1$, $3$, and $4$. Computing $w_\delta$ gives $30$, $10$, $10$. Now we should choose the category with the smaller index, i.e., category $3$, to ask. Since category $3$ is exactly the noun’s category, the user answers “Yes”, and we keep only category $3$ and all of its descendant categories. We find that at this point, more than one category remains, so the algorithm should continue. The remaining categories are $3$ and $4$, and computing $w_\delta$ gives $20$ and $0$. Therefore, we next ask about category $4$. Since category $3$ is not in the descendant categories of category $4$, the user answers “No”. We should then remove category $4$ and its descendant categories, keeping only category $3$. We find that only category $3$ remains, so the algorithm ends. The process is shown below: :::align{center}  ::: ### Subtasks For $20\%$ of the data, all category weights are equal, and the parent of every category is the root category. For another $20\%$ of the data, all category weights are equal, and each category has at most one subcategory. For $60\%$ of the data, $n \le 100$ and $m \le 10$. For $100\%$ of the data, $n \le 2000$, $m \le 100$, and $w_i \le 10^7$。 Note (not stated in the original statement): the first $40\%$ of the data also satisfy $n \le 100$ and $m \le 10$。 Translated by ChatGPT 5