405465: GYM101968 A Tree Game

Zagha and Hiasat are playing a game on a tree with $$$n$$$ nodes. At the beginning, both players are assigned a starting node on the tree, the two starting nodes are different, then both players take turns alternately. In each turn, the player chooses an unassigned adjacent node and merges it with his current node.

To merge node $$$a$$$ with node $$$b$$$, we remove the edge $$$(a,b)$$$, remove the node $$$b$$$, and then any edge $$$(b,x)$$$ for any node $$$x$$$ becomes $$$(a,x)$$$.

Zagha will start first, and the player who can't make a move loses. In how many ways we can choose the starting positions for Zagha and Hiasat such that Zagha is guaranteed to win (if both play optimally)?

The first line of input contains a single integer $$$T$$$ ($$$1 \le T \le 15000$$$), the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the size of the tree.

The second line contains $$$n-1$$$ space-separated integers $$$a_2,a_3,...,a_n$$$ ($$$1 \le a_i \le n$$$), representing that there is an edge between node $$$i$$$ and $$$a_i$$$.

The sum of $$$n$$$ over all test cases doesn't exceed $$$4\times10^6$$$.

For each test case, output a single line with the number of ways to choose the starting positions for Zagha and Hiasat such that Zagha is guaranteed to win.

3
2
1
3
1 2
5
5 1 3 3

0
4
13

In the second sample, there are 6 ways to choose the starting positions. Zagha is guaranteed to win in 4 of them.