20tps 求调
查看原帖
20tps 求调
1259871
jkZJM110211楼主2025/7/22 09:42
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int parent[MAXN];
vector<int> children[MAXN];
int depth[MAXN];
bool covered[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        cin >> parent[i];
        children[parent[i]].push_back(i);
    }

    queue<int> q;
    q.push(1);
    depth[1] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : children[u]) {
            depth[v] = depth[u] + 1;
            q.push(v);
        }
    }

    vector<pair<int, int>> nodes;
    for (int i = 1; i <= n; ++i) {
        nodes.emplace_back(depth[i], i);
    }
    sort(nodes.rbegin(), nodes.rend());

    int res = 0;
    for (auto& p : nodes) {
        int u = p.second;
        if (!covered[u]) {
            int v = parent[u];
            if (v != 0) {
                v = parent[v];
            }
            if (v == 0) {
                v = parent[u];
                if (v == 0) {
                    v = u;
                }
            }
            res++;
            queue<int> cover;
            cover.push(v);
            covered[v] = true;
            for (int i = 0; i < 2; ++i) {
                int size = cover.size();
                for (int j = 0; j < size; ++j) {
                    int x = cover.front();
                    cover.pop();
                    for (int y : children[x]) {
                        if (!covered[y]) {
                            covered[y] = true;
                            cover.push(y);
                        }
                    }
                    int px = parent[x];
                    if (px != 0 && !covered[px]) {
                        covered[px] = true;
                        cover.push(px);
                    }
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}
2025/7/22 09:42
加载中...