ACM模版

描述

题解

这个题和这一段时间的那个拉钩测评选择的最后一道题极其相似，那个题好像叫做监狱逃离，是一个七级算法，但是和这个题几乎是一样的，同样都是树，也都是树归，找一个结点作为根后开始深入，一直深入到最深层也就是说叶子结点后，开始回朔的过程中，不断进行状态的迁移，这里需要注意的是，两个题都是要考虑到同级子树的相互影响关系，这里的同级子树指得是根的父亲是同一个结点的多棵子树……这里我写的代码思路和标程略微差别，表示的是这个子树中离根最远的距离有多远，当根的距离大于等于 K 时，我们就在这个部位放置一个家丁，此时，将这个结点的状态置为 -K，因为我们知道每个家丁都可以控制 K 的范围，所以他还能向上控制 K 个，这里我们用负数表示，和标程恰好相反……具体代码不难理解，子树之间的作用关系和标程是相似的，没毛病~~~

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int N, K;
int ans;
int cnt = 0;
int dg[MAXN];           // 度
int dp[MAXN];
vector<int> vi[MAXN];

void dfs(int x, int pre)
{
    int max_ = -INF;
    int min_ = INF;
    for (int i = 0; i < vi[x].size(); i++)
    {
        if (vi[x][i] != pre)
        {
            dfs(vi[x][i], x);
            max_ = max(max_, dp[vi[x][i]]);
            min_ = min(min_, dp[vi[x][i]]);
        }
    }

    if (max_ == -INF)
    {
        max_ = min_ = 0;
    }

    if (max_ >= K)
    {
        ans++;
        dp[x] = -K;
    }
    else if (min_ < 0 && min_ + max_ < 0)
    {
        dp[x] = min_ + 1;
    }
    else
    {
        dp[x] = max_ + 1;
    }
}

int main()
{
// freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    cin >> N >> K;

    int x, y;
    for (int i = 1; i < N; i++)
    {
        scanf("%d%d", &x, &y);
        vi[x].push_back(y);
        vi[y].push_back(x);
        dg[x]++;
        dg[y]++;
    }

    dfs(0, -1);
    if (dp[0] > 0)
    {
        ans++;
    }

    printf("%d\n", ans);

    return 0;
}