Rockdu's Blog

17 3
1 2
3 2
2 4
5 2
5 6
5 8
7 8
9 8
5 10
10 13
13 14
10 12
12 11
15 17
15 16
15 10

13​​

 很好的一道题，果然我的贪心技巧还不够。

观察因为可以重叠，我们选叶子作为端点一定是最优的，因为如果不到叶子结点那么向叶子结点延伸一定可以覆盖更多点，因此在叶子很多的情况下我们选2*l个叶子。

接下来一步就比较巧妙了，我们换一个角度，从结果来思考。最后覆盖出的路径一定是从叶子向内延伸的，那么就算有再多的叶子只要上一层的节点数m<2*l那么也只能覆盖m个节点，并且之后也只能向上延伸m。因此我们对树拓扑排序算出每层的节点数模拟就行了。

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 1e6 + 5;
int n, l;
struct edge {
    int v, next;
} e[maxn << 1];

int head[maxn], cnt, ans, fa[maxn];
int depth[maxn], tot[maxn];
void adde(const int &u, const int &v) {
    e[++cnt] = (edge) {v, head[u]};
    head[u] = cnt;
}

int u, v, deg[maxn], vis[maxn], pos = -1;
queue<int > q;

int main() {
    scanf("%d%d", &n, &l);
    for(register int i = 1; i <= n - 1; ++i) {
        scanf("%d%d", &u, &v);
        adde(u, v), adde(v, u);
        ++deg[u], ++deg[v];
    }
    for(register int i = 1; i <= n; ++i)
        if(deg[i] == 1) q.push(i), ++tot[0], vis[i] = 1;
    while(!q.empty()) {
        int u = q.front(), v;
        q.pop();
        for(register int i = head[u]; i; i = e[i].next) {
            v = e[i].v;
            if(--deg[v] == 1) {
                q.push(v), vis[v] = 1;
                depth[v] = depth[u] + 1;
                ++tot[depth[v]];
            }
        }
    }
    for(register int i = 0; i <= n; ++i)
        ans += min(tot[i], 2 * l);
    printf("%d", ans);
    return 0;
}