## A Cousin Problem

View as PDF

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

Problem type

There are nodes with IDs from to . All nodes, with the exception of Node , has a parent node with an ID less than itself. Each node has a value. The node has a value of .

A ancestor of a node is defined as follows:

• If , the parent of the node
• If , the parent of the ancestor of the node

Two nodes are considered cousins if and only if their ancestors both exist and are the same node.

A node 's cousins is the set of all nodes for which and are cousins.

Answer queries, each asking: "Given and , what is the sum of the values cousins of ?"

#### Input Specification

The first line contains and .

The second line contains integers, the integer being .

The third line contains integers, the parents of Node to Node .

The next lines contain two integers each, and .

#### Output Specification

Print lines, the answers to the 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.