分析
首先我们知道如若当前点需要连边,那么一定是直接连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; }