求助鸽鸽们
查看原帖
求助鸽鸽们
366937
too_simple楼主2022/9/19 18:50

不知道贪心哪里错了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2e5 + 5;

int n, ans;
int ne[N], e[N], h[N], idx;
int fa[N];
bool check[N];

void add(int a, int b) {
    ne[idx] = h[a], e[idx] = b, h[a] = idx ++;
}

struct node {
    int dep, num;
    bool operator <(const node& jq) const {
        return dep > jq.dep;
    }
}po[N];

void dfs(int u, int father) {
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(j == father || j == 1) continue;
        po[j].dep = po[u].dep + 1;
        if(po[j].dep <= 2) {
            check[j] = true;
        }
        po[j].num = j;
        fa[j] = u;
        dfs(j, u);
    }
}

int main() {
    
    cin >> n;
    
    memset(h, -1, sizeof h);
    
    for(int i = 1; i <= n - 1; ++ i) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    check[1] = true;
    po[1].dep = 0;
    po[1].num = 1;
    
    dfs(1, -1);
    
    sort(po + 1, po + 1 + n);
    
    for(int i = 1; i <= n; ++ i) {
        if(check[po[i].num]) continue;
        ans ++;
        int u = fa[po[i].num];
        check[u] = true;
        for(int k = h[u]; ~k; k = ne[k]) {
            int j = e[k];
            check[j] = true;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}
2022/9/19 18:50
加载中...