题意

你有一颗 个节点的有根树 (以 号节点为根) ，求最少加入多少条边之后使得根节点（即 11 号节点）到这棵树上任意一点的距离不大于 。

分析

我们考虑覆盖一个节点有多少种方法。

• 在父亲节点连一条边。
• 在儿子节点上连一条边。
• 在当前节点上连一条边。

这样我们发现并不是很好做，考虑叶子节点。叶子节点只有两种可能，在自己或者在父亲上连一条边。那么我们很容易发现。在父亲处连边一定不劣于在当前节点建边。那么依次递归叶子节点就可以了，这样维护叶子节点通过 深度来维护。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {int x;scanf("%d",&x);return x;}
const int N = 2e5 + 100;
struct Edge {int to,nxt;}e[N << 1];
#define pii pair<int,int> 
pii A[N];// first -> dep , second -> id;
priority_queue<pii> Q;
int dis[N],fa[N],n,head[N],ecnt = 0;
void dfs(int x,int F,int D) {
    fa[x] = F;dis[x] = D;Q.push(pii(dis[x],x));
    for(int i = head[x];i;i = e[i].nxt) if(e[i].to ^ fa[x]) dfs(e[i].to,x,D + 1);
}
int main() {
    n = read();
    for(int i = 1,a,b;i < n;i++) {
        a = read();b = read();
        e[++ecnt] = (Edge){b,head[a]};head[a] = ecnt;
        e[++ecnt] = (Edge){a,head[b]};head[b] = ecnt;
    }
    dfs(1,0,0);int ans = 0;
    while(Q.size()) {
        int x = Q.top().second;Q.pop();
        if(dis[x] <= 2) continue;
        dis[fa[x]] = 0;ans++;
        for(int i = head[fa[x]];i;i = e[i].nxt) dis[e[i].to] = min(dis[e[i].to],1);
    }
    cout << ans << endl;
    return 0;
}

分析

对于不太敢相信贪心做法的（大雾）。这题也可以 。考虑 分别表示，当前节点的子树全部覆盖。 表示，自己没有建边，但是儿子覆盖到了自己。 表示当前节点建一条边。 表示，自己不建边，父亲建边。然后树形 扫一次就好了。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {int x;scanf("%d",&x);return x;}
const int N = 2e5 + 100,inf = 0x3f3f3f3f;
struct Edge {int to,nxt;}e[N << 1];
#define pii pair<int,int> 
int n,head[N],ecnt = 0,f[N][3];
void dfs(int x,int F,int dep) {
    f[x][0] = 0;if(dep < 2)f[x][1] = 0;else f[x][1] = 1;f[x][2] = 0;
    int res = inf,son = 0;
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(y == F) continue;
        dfs(y,x,dep + 1);
        f[x][1] += min(f[y][1],min(f[y][0],f[y][2]));
        if(f[x][2] < inf) f[x][2] += f[y][0];
        if(f[y][1] < f[y][0]) {f[x][0] += f[y][1];son = 1;}
        else f[x][0] += f[y][0];
        res = min(res,f[y][1] - f[y][0]);
    } 
    if(!son) f[x][0] += res;
}
int main() {
    n = read();
    for(int i = 1,a,b;i < n;i++) {
        a = read();b = read();
        e[++ecnt] = (Edge){b,head[a]};head[a] = ecnt;
        e[++ecnt] = (Edge){a,head[b]};head[b] = ecnt;
    }
    dfs(1,0,0);
    cout << min(f[1][1],f[1][0]) << endl;
    return 0;
}