A Cousin Problem

View as PDF

Submit solution

Points: 20
Time limit: 2.0s
Memory limit: 256M

Problem type

There are N nodes with IDs from 1 to N. All nodes, with the exception of Node 1, has a parent node with an ID less than itself. Each node has a value. The i^{\text{th}} node has a value of V_i.

A k^{\text{th}} ancestor of a node is defined as follows:

  • If k = 1, the parent of the node
  • If k > 1, the parent of the (k - 1)^{\text{th}} ancestor of the node

Two nodes are considered k^{\text{th}} cousins if and only if their k^{\text{th}} ancestors both exist and are the same node.

A node a's k^{\text{th}} cousins is the set of all nodes b for which a and b are k^{\text{th}} cousins.

Answer Q queries, each asking: "Given n and k, what is the sum of the values k^{\text{th}} cousins of n?"

Constraints

1 \leq N, Q \leq 200\ 000

1 \leq V_i \leq 10\ 000

1 \leq n, k \leq N

Input Specification

The first line contains N and Q.

The second line contains N integers, the i^{\text{th}} integer being V_i.

The third line contains N - 1 integers, the parents of Node 2 to Node N.

The next Q lines contain two integers each, n and k.

Output Specification

Print Q lines, the answers to the Q queries, in the order that they are given.

Sample Input

9 2
1 2 4 8 16 32 64 128 256
1 1 3 3 3 4 6 6
6 1
8 2

Sample Output

24
320

Credits

It turns out this problem is literally just Blood Cousins.


Comments