分析

首先我们知道如若当前点需要连边，那么一定是直接连1号点最优
接下来，我们考虑贪心，从底部向上进行
一个点需要被连边当且仅当它的儿子中有一个没有被覆盖到
（因为当前点和1连边之后只能多辐射一个距离内的点）
我们记录状态

• 0表示没有被子孙中的点覆盖
• 1表示被儿子覆盖
• 2表示没有被覆盖，需要父亲的人覆盖

那么我们直接进行dfs即可
每次记录儿子中状态的最小值即可
时间复杂度：
期望得分：100分

代码

//CF1029E
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define ll long long
#define cl(x, y) memset((x), (y), sizeof(x))
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
#define de(x) cerr << #x << " = " << x << " "
#define inc_mod(x, y) x = ((x - y) % mod + mod) % mod
#define add_mod(x, y) x = (x + y) % mod
#define mul_mod(x, y) x = (x * y) % mod
#define lowbit(x) (x & (-x))
#define inf 0x3f3f3f3f
#define mod 998244353
#define rson (x << 1 | 1)
#define lson (x << 1)
using namespace std;
const int maxn = 2e5 + 10;

int total, u, v, w, opt;
int nxt[maxn << 1], head[maxn], ed[maxn << 1], cur;
int dep[maxn], ans;

inline void file() {
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
}

inline void add_edge(int from, int to) {
    nxt[++cur] = head[from];
    head[from] = cur;
    ed[cur] = to;
}

inline int dfs(int now, int pre) {
    dep[now] = dep[pre] + 1;
    int res = 2;
    for(int i = head[now]; i; i = nxt[i]) {
        if(ed[i] == pre) continue;
        res = min(res, dfs(ed[i], now));
    }
    if(dep[now] >= 3 && !res) ans++;
    return (++res) % 3;
}

int main() {
    // file();
    ios::sync_with_stdio(false);
    cin >> total;
    rep(i, 2, total) {
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
    dfs(1, 0);
    cout << ans << endl;
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}