51nod1378 - 夹克老爷的愤怒（树型DP+贪心）

题目链接：

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1378

题目大意：

给出一张 N 个节点树形图，从中选若干个节点，使得途中任一节点距离最近的选中节点的距离不超过 K。

$1\le N\le 1e5, 0 \le K \le N$

题目分析：

树型DP，贪心的放，刚开始对于一颗子树，如果深度等于 K 那么肯定选中这颗子树的根节点。这时候这个选中的节点不仅对子孙节点有贡献，还对祖先或兄弟节点有贡献，这时候我们用一个数组 DP[i] 记录某个点可以做出多少贡献，或一个点需要多少的贡献。

比如选中了 u 节点，那么他具有 k 的贡献，他的父亲和孩子都有 k - 1的贡献。对于一个叶子节点视它为 0 点贡献，那么他的祖先就需要 -1 点贡献。

对于每个节点需要维护的是一颗子树的信息，要满足以它为根的子树里面的所有节点的需求。

通过以下方式进行转移：

minn = min(dp[child]), maxn = max(dp[child]);

如果当前节点为叶子节点，那么 minn = maxn = 0

if minn <= -k				#这时 u 的子树中已经有一个节点需求为 -k，如果不选中当前节点肯定无解
    dp[u] = k, ans++		
else if maxn + minn > 0		#这时 u 的子树中有一个节点的贡献可以满足其他节点的需求
    dp[u] = maxn - 1
else 						#如果不满足这两种情况，那么贪心的想，需求向祖先节点需求
	dp[u] = minn - 1

AC代码：

#include <bits/stdc++.h>

using namespace std;

const int MAX = 100000 + 100;
const int INF = 0x3f3f3f3f;

vector<int> edge[MAX];

int dp[MAX];

int ans = 0;
int n, k;

void dfs(int u, int fa) {
    int minn = INF;
    int maxn = -INF;
    bool ok = false;
    for (auto v : edge[u]) {
        if (v == fa) continue;
        dfs(v, u);
        ok = true;
        minn = min(dp[v], minn);
        maxn = max(dp[v], maxn);
    }

    if (!ok) maxn = minn = 0;
    if (minn <= -k) dp[u] = k, ans++;
    else if (maxn + minn > 0) dp[u] = maxn - 1;
    else dp[u] = minn - 1;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(0, -1);
    if (dp[0] < 0) ans++;
    printf("%d\n", ans);
}

解题过程：

在白书上看到了一个类似的题，然后扩展了一下，去群里问了下做法，感觉应该是很经典的题，然后人形题库 qls 就给出 51nod 上的原题，于是就补了一下。还是有一个坑点的，如果直接不考虑叶子节点的话，对于 k = 0 的情况需要特判。