Non-Ancestor Matching

AtCoder

IDarc205_d

Time2000ms

Memory256MB

Difficulty—

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. You can perform the following sequence of operations zero or more times. * Choose a pair of integers $(u,v)$ that satisfies all of the following conditions. * $1\le u < v \le N$ * Both vertices $u$ and $v$ are colored white. * $u$ is **not** an ancestor of $v$. * Color vertices $u$ and $v$ black. Here, "$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. Find the maximum number of operations you can perform when you perform operations in an appropriate order. You are given $T$ test cases, so find the answer for each of them. ## Constraints * $1\le T\le 5\times 10^4$ * $2\le N\le 5\times 10^5$ * $1\le p_i < i$ * The sum of $N$ over all test cases is at most $5\times 10^5$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ Each test case $\text{case}_i$ is given in the following format: $N$ $p_2$ $p_3$ $\ldots$ $p_N$ [samples]

Samples

Input #1

4
6
1 2 2 2 5
7
1 2 3 4 5 6
7
1 2 3 4 2 4
12
1 1 2 2 2 4 4 4 7 7 7

Output #1

2
0
2
5

Consider the first test case.
![image](https://img.atcoder.jp/arc205/6734339acfecc9c4c7ae80a268dda726.png)
You can perform two operations as follows.

*   Choose $(u,v)=(3,5)$. Color vertices $3$ and $5$ black.
*   Choose $(u,v)=(4,6)$. Color vertices $4$ and $6$ black.

You cannot perform more than two operations, so output $2$ on the first line.

API Response (JSON)

{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments