TRIBT  Triangle on Binary Tree
You are given a parent array P of length N that represents a binary tree with N nodes, which may be unbalanced, balanced, complete or full. The array indexes are values in tree nodes and the array values represent the parent node of that particular index, a value 1 means that particular index is the root of the tree. This gives both left child and right child or only left child, for a parent, right child cannot exist without left child. You are required to count the total number of potential isosceles triangles in the binary tree. A potential isoscele triangle is the two sides of equal length must be formed by two paths of equal length from a parent or root. Due to the nature of binary tree, not three sides are connected, you can just ignore the remaining unconnected side.
Consider a parent array [1, 5, 5, 2, 2, 1, 3], it constructs a binary tree like:
There are 4 potential isosceles triangles in total, they are (1, 5, 2), (0, 5, 4), (3, 2, 4) and (3, 2, 5) respectively.
Input
The first line is the number of test cases T. (1 <= T <= 50)
For each test case, it starts with one integer representing the number of nodes or length of the array N. (1 <= N <= 10^{5})
The next line has N integers, P_{i} is the node's parent node (1 is the root) and i is its value. (1 <= P_{i} <= N  1)
Output
Print the total number of potential isosceles triangles.
Example
Input: 3 7 1 5 5 2 2 1 3 20 1 0 0 1 1 3 5 4 7 4 8 8 9 10 10 9 15 15 16 16 5 3 0 1 1 2
Output: 4 20 0
Explanation
Let's visualize the sample input:
Case 1 is just the sample mentioned above.
Case 2 has 20 potential isosceles triangels: (1, 0, 2), (3, 1, 4), (5, 1, 9), (6, 1, 15), (7, 4, 9), (8, 4, 15), (10, 4, 17), (12, 9, 15), (10, 8, 11), (16, 15, 17), (13, 10, 14), (18, 16, 19), (4, 1, 0), (1, 4, 7), (4, 9, 12), (7, 8, 11), (9, 15, 16), (8, 10, 14), (15, 16, 19) and (4, 15, 18).
Case 3 has no triangles.
hide comments
nadstratosfer:
20190220 12:34:55
Beware of blanklines in input when solving in Python. 

julkas:
20181103 15:55:50
+5 

mehmetin:
20180503 05:08:59
Images don't show. 
Added by:  him0727 
Date:  20180413 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own problem 