Graph Theory 6

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

You are given a directed acyclic graph of N + 1 nodes numbered from 0 to N and you need to perform Q queries on it. Node 0 has a value of 0, and every other node has a value of v_i. Every node only has 1 child. Find the sum of values of a node and all of its children.

Input Specification

The first line will contain the integer N, Q\ (1 \le N, Q \le 10^5), the number of nodes and the number of queries.

The next N lines describes which nodes are connected. The K^{th} line contains the integers v_i, i\ (1 \le v_i \le 10^5),\ (0 \le i \le N), where i is the K^{th} node's child.

The next Q lines contains an integer j\ (1 \le j \le N), the node to query.

Output Specification

For every query, print the sum of values of the node and all of its children.

Sample Input

5 5
1 0
2 0
4 1
8 2
16 3
1
2
3
4
5

Sample Output

1
2
5
10
21

Subtasks

Subtask 1 [30%]

(1 \le N, Q \le 10^3)

Subtask 2 [70%]

No further constraints.


Comments

There are no comments at the moment.