Victor and Proposition

At the very beginning, Victor has a proposition, then this proposition procudes many propositions. Then every proposition procudes more propositions...... Finally there are $n$ propositions. These propositions can be regarded as a tree whose root is $1$.

We assume that the first proposition, whose number is $1$, belongs to the $0$-th generation, and those propositions produced by the $x$-th generation belong to the $x+1$-th generation. We also assume that all of the propositions in the $x$-th generation are in level $x$. Specially, Victor has discovered that the proposition whose number is $i$ can infer the proposition whose number is $x_i$ and all of the propositions in $x_i$'s subtree, whose levels are not greater than $x_i$'s level + $d_i$.

Notice : $a$ is $b$'s father does not show that either $a$ can infer $b$ or $b$ can infer $a$.

Now please determine the number of such ordered pairs $(i,j)$, that $1\leq i < j\leq n$, the proposition $i$ can infer the proposition $j$, and the proposition $j$ can also infer the proposition $i$.

The first line of the input contains an integer $T$, denoting the number of test cases.

In every test case, there is an integer $n$ in the first line, denoting the number of the propositions.

The second line contains $n-1$ integers, the $i$-th integer $f_{i+1}(f_i < i)$ denotes that the proposition $i+1$ is produced by the proposition $f_{i+1}$.

Then there are $n$ lines, the $i$-th line contains two integers $x_i$ and $d_i$.

$1\leq T\leq 5$.

$2\leq n\leq 100000$.

$0\leq d_i < n$.

Your program should print $T$ lines : the $i$-th of these should contain a single integer, denoting the number of such ordered pairs $(i,j)$.

1
4
1 2 1
2 1
1 0
4 0
2 0

6

If you need a larger stack size,
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

BestCoder Round #52 (div.2)