{"problem":{"name":"Non-Ancestor Matching","description":{"content":"You are given a rooted tree with $N$ vertices numbered from $1$ to $N$. Vertex $1$ is the root, and the parent of vertex $i$ $(2 \\le i \\le N)$ is vertex $p_i$ $(1\\le p_i < i)$. Initially, all vertices","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc205_d"},"statements":[{"statement_type":"Markdown","content":"You are given a rooted tree with $N$ vertices numbered from $1$ to $N$. Vertex $1$ is the root, and the parent of vertex $i$ $(2 \\le i \\le N)$ is vertex $p_i$ $(1\\le p_i < i)$. Initially, all vertices are colored white.\nYou can perform the following sequence of operations zero or more times.\n\n*   Choose a pair of integers $(u,v)$ that satisfies all of the following conditions.\n    *   $1\\le u < v \\le N$\n    *   Both vertices $u$ and $v$ are colored white.\n    *   $u$ is **not** an ancestor of $v$.\n*   Color vertices $u$ and $v$ black.\n\nHere, \"$u$ is not an ancestor of $v$\" means that you cannot reach vertex $u$ from vertex $v$ no matter how many times you perform the operation of moving to the parent of the current vertex.\nFind the maximum number of operations you can perform when you perform operations in an appropriate order.\nYou are given $T$ test cases, so find the answer for each of them.\n\n## Constraints\n\n*   $1\\le T\\le 5\\times 10^4$\n*   $2\\le N\\le 5\\times 10^5$\n*   $1\\le p_i < i$\n*   The sum of $N$ over all test cases is at most $5\\times 10^5$.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case $\\text{case}_i$ is given in the following format:\n\n$N$\n$p_2$ $p_3$ $\\ldots$ $p_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc205_d","tags":[],"sample_group":[["4\n6\n1 2 2 2 5\n7\n1 2 3 4 5 6\n7\n1 2 3 4 2 4\n12\n1 1 2 2 2 4 4 4 7 7 7","2\n0\n2\n5\n\nConsider the first test case.\n![image](https://img.atcoder.jp/arc205/6734339acfecc9c4c7ae80a268dda726.png)\nYou can perform two operations as follows.\n\n*   Choose $(u,v)=(3,5)$. Color vertices $3$ and $5$ black.\n*   Choose $(u,v)=(4,6)$. Color vertices $4$ and $6$ black.\n\nYou cannot perform more than two operations, so output $2$ on the first line."]],"created_at":"2026-03-03 11:01:14"}}