{"problem":{"name":"A. Tree Game","description":{"content":"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 turn","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10196A"},"statements":[{"statement_type":"Markdown","content":"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.\n\nTo 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)$.\n\nZagha 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)?\n\nThe first line of input contains a single integer $T$ ($1 <= T <= 15000$), the number of test cases.\n\nThe first line of each test case contains a single integer $n$ ($1 <= n <= 10^6$), the size of the tree.\n\nThe second line contains $n -1$ space-separated integers $a_2, a_3,..., a_n$ ($1 <= a_i <= n$), representing that there is an edge between node $i$ and $a_i$.\n\nThe sum of $n$ over all test cases doesn't exceed $4 times 10^6$.\n\nFor 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.\n\nIn the second sample, there are 6 ways to choose the starting positions. Zagha is guaranteed to win in 4 of them.\n\n## Input\n\nThe first line of input contains a single integer $T$ ($1 <= T <= 15000$), the number of test cases.The first line of each test case contains a single integer $n$ ($1 <= n <= 10^6$), the size of the tree.The second line contains $n -1$ space-separated integers $a_2, a_3,..., a_n$ ($1 <= a_i <= 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 times 10^6$.\n\n## Output\n\nFor 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.\n\n[samples]\n\n## Note\n\nIn the second sample, there are 6 ways to choose the starting positions. Zagha is guaranteed to win in 4 of them.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n = |V| $ nodes.  \nLet $ S \\subseteq V \\times V $ be the set of ordered pairs $ (u, v) $ such that $ u \\ne v $, representing possible starting positions for Zagha ($ u $) and Hiasat ($ v $).  \n\n**Game Rules**  \n- Players alternate turns, Zagha moves first.  \n- On a turn, a player must choose an *unassigned* neighbor of their current node and *merge* it into their node (removing the edge and the merged node, redirecting its other edges).  \n- A player loses if they cannot make a move.  \n- All moves are optimal.  \n\n**Objective**  \nCount the number of ordered pairs $ (u, v) \\in S $ such that Zagha has a winning strategy under optimal play.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 15000 $  \n2. For each test case: $ 1 \\le n \\le 10^6 $, and the sum of all $ n $ across test cases $ \\le 4 \\times 10^6 $  \n3. The tree is given via parent representation: for $ i = 2 $ to $ n $, node $ i $ is connected to node $ a_i $  \n\n**Output**  \nFor each test case, output the number of starting position pairs $ (u, v) $ where Zagha wins.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10196A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}