HackerRank : Week of Code 23 – Gravity Tree

By | September 16, 2016

Sarah is young scientist in Neverland who just invented a gravity tree with the following properties:

  • It’s a tree where each vertex is numbered from to and vertex always denotes the root. Each edge has a length of , so a node has a distance of from its parent, a distance of from its grandparent, and so on.
  • Some vertex, , can be turned on, which results in all vertices (including ) of the subtree rooted at beginning to attract the tree’s other vertices. The attractive forces exerted on some vertex, , is equal to the summation of squared distances between vertex and all vertices that are currently switched on (i.e., all nodes in the subtree rooted at ). For example, if two nodes are switched on that have distances of and from node , then the forces exerted on would be .

Sarah wants to test the tree by carrying out a series of experiments on pairs of vertices, and . In each experiment, she turns on vertex and measures the forces acting on vertex before immediately turning back off. To avoid undesirable consequences, she wants to know the value of this attractive forces in advance.

Given the definition of her gravity tree and experiments, print the value of the attractive forces between vertices and for each experiment on a new line. Note that each experiment is independent and no experiment will affect the subsequent experiments.

Input Format

The first line contains a single integer, , denoting the number of vertices in the tree.
The second line contains space-separated integers where the integer denotes the parent vertex of vertex .
The next line contains an integer, , denoting the number of experiments she plans to perform.
Each of the subsequent lines contains two space-separated integers denoting the respective values of and for an experiment.

Constraints

Output Format

On a new line for each experiment, print a single integer denoting the expected value of the forces acting on vertex from all the nodes in the subtree rooted at vertex .

Sample Input

5
1 2 2 4
2
2 1
1 4

Sample Output

7 
13

Explanation

The diagram below depicts the tree defined in the Sample Case:

Let be the shortest distance from some vertex to vertex , where is a turned on vertex in the subtree rooted at . Sarah will perform the following experiments:

  1. Turn on vertex and measure the forces acting on vertex . When vertex is on, all the vertices in the tree (i.e., ,, , , and ) generate attractive forces. We then calculate the forces acting on vertex as:

    Thus, we print on a new line.

  2. Turn on vertex and measure the forces acting on vertex . When vertex is on, the vertices in the subtree rooted at (i.e., and ) generate attractive forces. We then calculate the forces acting on vertex as:

    Thus, we print on a new line.