{"raw_statement":[{"iden":"statement","content":"Alex is a professional computer game player.\n\nThese days, Alex is playing a war strategy game. The kingdoms in the world form a rooted tree. Alex's kingdom $1$ is the root of the tree. With his great diplomacy and leadership, his kingdom becomes the greatest empire in the world. Now, it's time to conquer the world!\n\nAlex has almost infinite armies, and all of them are located at $1$ initially. Every week, he can command one of his armies to move one step to an adjacent kingdom. If an army reaches a kingdom, that kingdom will be captured by Alex instantly.\n\nAlex would like to capture all the kingdoms as soon as possible. Can you help him?\n\nThe first line of the input gives the number of test cases, $T \" \"(1 <= T <= 10^5)$. $T$ test cases follow.\n\nFor each test case, the first line contains an integer $n \" \"(1 <= n <= 10^6)$, where $n$ is the number of kingdoms in the world.\n\nThe next line contains $(n -1)$ integers $f_2, f_3, \\\\\\\\cdots, f_n \" \"(1 <= f_i < i)$, representing there is a road between $f_i$ and $i$.\n\nThe sum of $n$ in all test cases doesn't exceed $5 times 10^6$.\n\nFor each test case, output one line containing \"_Case #x: y_\", where $texttt(x)$ is the test case number (starting from $1$), and $texttt(y)$ is the minimum time to conquer the world.\n\n"},{"iden":"input","content":"The first line of the input gives the number of test cases, $T \" \"(1 <= T <= 10^5)$. $T$ test cases follow.For each test case, the first line contains an integer $n \" \"(1 <= n <= 10^6)$, where $n$ is the number of kingdoms in the world.The next line contains $(n -1)$ integers $f_2, f_3, \\\\\\\\cdots, f_n \" \"(1 <= f_i < i)$, representing there is a road between $f_i$ and $i$.The sum of $n$ in all test cases doesn't exceed $5 times 10^6$."},{"iden":"output","content":"For each test case, output one line containing \"_Case #x: y_\", where $texttt(x)$ is the test case number (starting from $1$), and $texttt(y)$ is the minimum time to conquer the world."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ n \\in \\mathbb{Z} $ be the number of kingdoms, with kingdom $ 1 $ as the root.  \nLet $ G = (V, E) $ be a rooted tree with $ V = \\{1, 2, \\dots, n\\} $, where for each $ i \\in \\{2, \\dots, n\\} $, there is an edge between $ i $ and $ f_i $, and $ f_i < i $.  \nLet $ \\text{deg}(v) $ denote the degree of node $ v $ in $ G $.  \nLet $ d(v) $ denote the depth of node $ v $ (distance from root $ 1 $).\n\n**Constraints**  \n1. $ 1 \\le T \\le 10^5 $  \n2. $ 1 \\le n \\le 10^6 $ for each test case  \n3. $ \\sum_{\\text{all test cases}} n \\le 5 \\times 10^6 $  \n4. For each $ i \\in \\{2, \\dots, n\\} $, $ 1 \\le f_i < i $\n\n**Objective**  \nFind the minimum number of weeks required for one army, starting at node $ 1 $, to visit all nodes in $ G $, where each week the army moves along one edge. The army may revisit nodes, but each node must be visited at least once.\n\nThe minimum time is:  \n$$\n2(n - 1) - \\max_{v \\in V} d(v)\n$$","simple_statement":"Alex starts at kingdom 1 with infinite armies. Each week, one army can move one step to an adjacent kingdom. When an army arrives at a kingdom, it’s captured instantly. Find the minimum weeks needed to capture all kingdoms in a tree.","has_page_source":false}