P6041 "ACOI2020" Pudding Assassination Plan

 Kayano Kaede (茅野 カエデ) made a plan to assassinate Koro-sensei using pudding. They used the remaining eggs to make a pudding. For appearance and taste, they add some ingredients wrapped in rice paper to change the flavor. For better looks, these ingredients are arranged from top to bottom in the shape of a tree. At the very bottom of the pudding, it is filled with bombs for Koro-sensei. When Koro-sensei eats to that part, it will explode.

Finally, the students finished the pudding. Kaede, who loves pudding the most, started thinking: how tasty is this pudding? How tasty a pudding is depends on the flavor-changing ingredients inside. Different ingredients have different colors and tastiness values. There are $n$ kinds of flavoring ingredients in the pudding, connected by $n-1$ links. The first ingredient is at the top, which is the root of this tree. Now, Kaede defines that the tastiness of the pudding depends on two given values $u, k$. This tastiness is defined as follows: let $v$ be the $k$-th ancestor of ingredient $u$. Consider all $k$-th level children of ingredient $v$, and among them, take those $k$-th level children whose color is the same as the color of ingredient $v$. The answer is the sum of the tastiness values of these selected nodes. It can be seen that when $u$ or $k$ changes, in general the tastiness value also changes. Therefore, there are $q$ queries to ask you. **In particular, if ingredient $u$ does not have a $k$-th ancestor, output $0$ directly.**

The first line contains two integers $n, q$, meaning there are $n$ ingredients and $q$ queries. The second line contains $n$ integers. The $i$-th integer represents the color of ingredient $i$, $color_i$. The third line contains $n$ integers. The $i$-th integer represents the tastiness value of ingredient $i$, $d_i$. The fourth line contains $n-1$ integers. The $i$-th integer represents the parent node of the ingredient $i+1$, $fa_i$. The next $q$ lines each contain two integers $u, k$, representing a query.

There are $q$ lines, each containing one integer, representing the answer to the query.

#### Sample Explanation #1  The $1$-st ancestor of ingredient $2$ is ingredient $1$. The $1$-st level children of ingredient $1$ are ingredients $2$ and $3$. The colors of ingredients $2$ and $3$ are both the same as the color of ingredient $1$, so the sum of tastiness values is $2 + 3 = 5$. ------------ #### Constraints **This problem uses bundled testdata.** - Subtask 1 (30 points): Eggs are scarce, the pudding is small: $n \leq 10^3$, $q \leq 10^4$. - Subtask 2 (20 points): The ingredients form a chain: $n \leq 5 \times 10^5$, $q \leq 10^5$, $color_i \leq 10^2$. - Subtask 3 (50 points): No special restrictions on the testdata. For $100\%$ of the testdata, $1 \leq n, q, color_i \leq 5 \times 10^5$, $1 \leq d_i \leq 10^5$. ------------ #### Hint **The time limit for the test points in Subtask 2 and Subtask 3 is 2S.** Translated by ChatGPT 5