CF1029E Tree with Small Distances 题解

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 1048600;
vector<int> adj[N];
int depth[N], parent[N];
int vis[N];
void dfs(int u, int fa) {
    depth[u] = depth[fa] + 1;
    parent[u] = fa;
    for (int &v : adj[u])
        if (v != fa) dfs(v, u);
}
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    dfs(1, 0);
    priority_queue<pair<int, int>> q;
    for (int i = 1; i <= n; ++i)
        if (depth[i] > 3) q.emplace(depth[i], i);
    int cnt = 0;
    while (q.size()) {
        auto [y, x] = q.top();
        q.pop();
        if (vis[x]) continue;
        x = parent[x];
        ++cnt;
        vis[x] = 1;
        for (int &i : adj[x]) vis[i] = 1;
    }
    cout << cnt << '\n';
    return 0;
}