Not another LCA problem

After watching the Jurassic World movie trailer, Xorin decided about the subject of his PhD thesis. While he was doing his research, he solved some of the finest problems on MindCoding: The Oddest Tree and Bosses, so he fell in love with the problem of finding the Lowest Common Ancestor of a tree.

It didn't take long for Xorin to find out that there was another species of dinosaurs which lived 232 years ago (only Xorin knows the magic formula for determining that number). Being very excited, he named that species Xorinosaurus. He was very fascinated about Xorinosaurus, especially because they were Blativores, which means they only ate the leaves of a very rare and special tree called Blat which is, in fact, a simple tree.

Xorin's research paper about Xorinsaurus is almost done, he only has to write something about Blat trees. Because Xorin is afraid of them, it went naturally for Xorin to call Comisia and ask her to help with the following problem:

You are given a rooted Blat tree T with N nodes. The nodes are numbered from 1 to N. Each node has an integer Value attached to it. Also, for every node X of the tree, you are given another value, call it BigValue, and you have to output the number of ordered pairs (a, b) such that the Value in a and b is less or equal than BigValue, and further, LCA(a, b) = X. Note that a can equal b.

At first, Comisia was afraid of this problem because she couldn't come up with a polynomial algorithm, so it's your task, as a MindCoding finalist participant, to solve it and help Xorin finish his PhD after 11 years of struggle (he started working on the thesis in 2004, but the subject has been chosen only a few months ago). If you manage to do so, Comisia and Xorin will congratulate you with a lot of points.


The input contains four lines.

The first line of input contains integer N.
The second line of input contains a sequence of N - 1 numbers. The kth number is the direct father of the k + 1 node. Also keep in mind that 1 ≤ kth number ≤ k.
The third line has N values representing the Value assigned to every node.
The fourth line has N values representing the BigValue assigned for every node.


You'll have to output N lines.
For each node X, in increasing order, you should output a single number (the answer to the problem) followed by a newline character.


  • The root of T is 1
  • 1 <= N <= 105
  • -260 <= Value, BigValue of each node <= 260
  • The order in which the nodes appear in the pair is significant: the ordered pair (a, b) is different from the ordered pair (b, a) unless a = b, as explained here.
  • No, this is not Comisia!
  • It is guaranteed that T is a Blat Tree


1 1 2 2
2 7 6 10 11
10 11 8 9 13

For the second node of the tree the requested pairs are the following:
(2, 2), (2, 4), (2, 5)
(4, 2), (4, 5)
(5, 2), (5, 4)
as for each pair the lca of nodes equals 2 and the value in both nodes is less than or equal to 11.

For the root of the tree, the requested pairs are:
(1, 1), (1, 2), (1, 3), (1, 4)
(2, 1), (2, 3)
(3, 1), (3, 2), (3, 4)
(4, 1), (4, 3)


Sponsors Gold