P3942 将军令

梦里，小 F 成了一个给将军送密信的信使。

现在，有两封关乎国家生死的密信需要送到前线大将军帐下，路途凶险，时间紧迫。小 F 不因为自己的祸福而避趋之，勇敢地承担了这个任务。

不过，小 F 实在是太粗心了，他一不小心把两封密信中的一封给弄掉了。

小 F 偷偷打开了剩下的那封密信。他发现一副十分详细的地图，以及几句批文——原来这是战场周围的情报地图。他仔细看后发现，在这张地图上标记了 n 个从 1 到 n 标号的驿站，n − 1 条长度为 1 里的小道，每条小道双向连接两个不同的驿站，并且驿站之间可以通过小道两两可达。

小 F 仔细辨认着上面的批注，突然明白了丢失的信的内容了。原来，每个驿站都可以驻扎一个小队，每个小队可以控制距离不超过 k 里的驿站。如果有驿站没被控制，就容易产生危险——因此这种情况应该完全避免。而那封丢失的密信里，就装着朝廷数学重臣留下的精妙的排布方案，也就是用了最少的小队来控制所有驿站。

小 F 知道，如果能计算出最优方案的话，也许他就能够将功赎过，免于死罪。他找到了你，你能帮帮他吗？当然，小 F 在等待你的支援的过程中，也许已经从图上观察出了一些可能会比较有用的性质，他会通过一种特殊的方式告诉你。

Solution

很早做的题，那时没博客

今天做了类似的，貌似数据有点问题。。

好的这题可以贪心

我们从深度大的节点开始，可以发现在深度与这个节点差 \(\leq k\) 的节点驻扎，此点可以被控制

那么当然染最远那个点优，可以够得到上面一点的点

于是从深度大的开始，若没被染色则上访到最远处，染色，顺便将能染得都染了

顺便累计答案即可

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

typedef long long LL;

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 1000019,INF = 1e9;

int head[maxn],nume = 1;

struct Node{

    int v,dis,nxt;

    }E[maxn << 3];

void add(int u,int v,int dis){

    E[++nume].nxt = head[u];

    E[nume].v = v;

    E[nume].dis = dis;

    head[u] = nume;

    }

int num,k;

int fa[maxn];

struct T{

    int index,dep;

    }I[maxn];

bool cmp(T a,T b){return a.dep > b.dep;}

bool vis[maxn];

int dep[maxn];

void dfs1(int u,int F){

    for(int i = head[u];i;i = E[i].nxt){

        int v = E[i].v;

        if(v == F)continue;

        I[v].dep = dep[v] = I[u].dep + 1;

        dfs1(v,u);

        }

    }

bool used[maxn];

void dfs2(int u,int left){

    vis[u] = 1;

    used[u] = 1;

    for(int i = head[u];i;i = E[i].nxt){

        int v = E[i].v;

        if(!used[v] && left > 0)dfs2(v,left - 1);

        }

    used[u] = 0;

    }

int col;

void find(int u,int left){

    col = u;

    if(left == 0)return ;

    for(int i = head[u];i;i = E[i].nxt){

        int v = E[i].v;

        if(dep[v] > dep[u])continue;

        find(v,left - 1);

        }

    }

int ans;

void check(){

    for(int i = 1;i <= num;i++){

        if(!vis[I[i].index]){

            ans++;

            find(I[i].index,k);

            dfs2(col,k);

            }

        }

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

    }

int main(){

    num = RD();k = RD();RD();

    for(int i = 1;i <= num - 1;i++){

        int u = RD(),v = RD();

        add(u,v,1);add(v,u,1);

        I[i].index = i;//这里和输入路径无关

        }

    I[num].index = num;

    I[1].dep = dep[1] = 1;

    dfs1(1,-1);

    sort(I + 1,I + 1 + num,cmp);

    check();

    return 0;

    }