外卖业务

struct Node {
    int parent;
    vector<int> sons;
};

static constexpr int NO = 0, LIGHTED = 1;

int main(int argc, char const* argv[]) {
    std::ios::sync_with_stdio(false);
    auto T = 0;
    cin >> T;
    while (T--) {
        auto M = 0;
        cin >> M;
        vector<Node> nodes(M + 1);
        for (auto i = 2; i <= M; i++) {
            auto& snode = nodes[i];
            auto p = 0;
            cin >> p;
            auto& pnode = nodes[p];
            pnode.sons.push_back(i);
            snode.parent = p;
        }
        if (M == 1) {
            cout << 1 << std::endl;
            continue;
        }
        // 首先找到所有的叶子节点
        vector<int> inds(M + 1, 0);
        vector<int> colors(M + 1, 0);
        std::queue<int> q, nq;
        for (auto i = 1; i <= M; i++) {
            auto const& node = nodes[i];
            inds[i] = static_cast<int>(node.sons.size());
            if (inds[i] == 0) {
                q.push(i);
            }
        }

        auto ans = 0;
        while (!q.empty()) {
            while (!q.empty()) {
                auto const& nid = q.front();
                q.pop();
                auto const& node = nodes[nid];
                // 判断当前节点是否要上色
                auto need = 0;
                if (colors[nid] == NO) {
                    if (node.parent >= 1) {
                        need = 2;
                    } else {
                        need = 1;
                    }
                } else {
                    // 如果有一个孩子没有 color
                    auto const& nodesons = node.sons;
                    for (auto const& s : nodesons) {
                        if (colors[s] == NO) {
                            need = 1;
                            break;
                        }
                    }
                }
                if (need == 1) {
                    // 需要上色, 那么先上色
                    ans++;
                    // 自己
                    colors[nid] = LIGHTED;
                    // 所有父亲
                    if (node.parent >= 1) {
                        colors[node.parent] = LIGHTED;
                        auto const& parentnode = nodes[node.parent];
                        if (parentnode.parent >= 1) {
                            colors[parentnode.parent] = LIGHTED;
                        }
                    }
                    // 孩子不上色
                } else if (need == 2) {
                    // 依赖父亲上色
                    colors[node.parent] = LIGHTED;
                }
                // 做完, pop
                if (node.parent >= 1) {
                    inds[node.parent]--;
                    if (inds[node.parent] == 0) {
                        nq.push(node.parent);
                    }
                }
            }
            q.swap(nq);
        }
        cout << ans << std::endl;
    }
    return 0;
}