greedy_spy.cpp

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    scanf("%d", &n);

    // read input
    int par[n];
    par[0] = -1;
    for (int i = 1; i < n; i++)
        scanf("%d", &par[i]);

    int ans = 0;
    // traverse from the back of the list -> start from the leaf
    for (int i = n - 1; i > 0; i--) {
        if (par[i] >= 0) { // if the current leaf node has a parent
            ans++; // let's select this node's parent as a node for monitoring

            for (int j = 1; j < n; j++) {
                // we erase all children of the node we just selected (set to -1)
                if (i != j && par[j] == par[i]) {
                    par[j] = -1;
                }
            }

            if (par[i] != 0)
                par[par[i]] = -1;
            par[i] = -1;
        }
    }

    printf("%d\n", ans);
}

int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--)
        solve();

    return 0;
}