Matt Damon in Mars
All submissions for this problem are available.
Matt Damon wants to escape Mars!! Desperately!!
While he was collecting an award for his performance in "The Martian", Matt Damon found himself teleported all of a sudden to Mars. And now he has no means to get back to earth.
However, Matt Damon has a unique Force Tree to help him with his esacpe attempts. A force tree has the following properties:
- It's a tree where each vertex is numbered from 1 to n and vertex 1 always denotes the root. Each edge has a length of 1, so a node has a distance of 1 from its parent, a distance of 2 from its grandparent, and so on.
- Some vertex, v , can be turned on, which results in all vertices (including v) of the subtree rooted at v beginning to attract the tree's other vertices. The attractive forces exerted on some vertex , u , is equal to the summation of squared distances between vertex u and all vertices that are currently switched on (i.e., all nodes in the subtree rooted at v ).
For example, if two nodes are switched on that have distances of 1 and 2 from node u, then the forces exerted on u would be 1*1 + 2*2 =5.
Matt wants to test the tree by carrying out a series of experiments on pairs of vertices, u and v. In each experiment, he turns on vertex v and measures the forces acting on vertex u before immediately turning v back off. To avoid undesirable consequences, he wants to know the value of this attractive forces in advance.
Given the definition of his force tree and q experiments, print the value of the attractive forces between vertices u and v for each experiment on a new line. Note that each experiment is independent and no experiment will affect the subsequent experiments.
The first line contains a single integer n, denoting the number of vertices in the tree.
The second line contains n-1 space-separated integers where kth the integer denotes the parent vertex of vertex k+1.
The next line contains an integer q, denoting the number of experiments he plans to perform.
Each of the q subsequent lines contains two space-separated integers denoting the respective values of u and v for an experiment.
On a new line for each experiment, print a single integer denoting the expected value of the forces acting on vertex u from all the nodes in the subtree rooted at vertex v.
- 1 ≤ n, q ≤ 10^5
Input: 5 1 2 2 4 2 2 1 1 4 Output: 7 13
Let di,u be the shortest distance from some vertex i to vertex u, where i is a turned on vertex in the subtree rooted at v. Matt will perform the following q=2 experiments:
- Turn on vertex 1 and measure the forces acting on vertex 2. When vertex 1 is on, all the vertices in the tree (i.e., 1, 2, 3, 4 and 5) generate attractive forces. We then calculate the forces acting on vertex 2 as:
(d1,2)2 + (d2,2)2 + (d3,2)2 + (d4,2)2 + (d5,2)2 = 12 + 02 + 12 + 12 + 22 = 7
Thus, we print 7 on a new line.
- Turn on vertex 4 and measure the forces acting on vertex 1. When vertex 4 is on, the vertices in the subtree rooted at 4 (i.e., 4 and 5) generate attractive forces. We then calculate the forces acting on vertex 1 as:
(d4,1)2 + (d5,1)2 = 22 + 32 = 13 Thus, we print 13 on a new line.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions