[Luogu3942]将军令

Posted on | In

一道难度适中的小清新乱搞好题

这题的正解是贪心，不过我好像$Hack$了正解

贪心策略好像还是比较简单的

找到当前没被覆盖的深度最深的点

然后找到它的$K$级父亲，往周围标记距离在$K$以内的点

如果有更优的标记，即离每次开始标记的点更近

那么就暴力更新标记，知道全部的点都被标记为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
const int maxn=200002;
int n,k,t,ans,cnt,f[maxn],Q[maxn],fa[maxn],to[maxn],from[maxn],head[maxn];
inline void add(int u,int v) {
    from[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
}
inline void bfs() {
    Q[1]=1; fa[1]=1;
    int he=1,ta=2;
    while(he<ta) {
        int x=Q[he++];
        for(register int i=head[x];i;i=from[i])
            if(!fa[to[i]]) fa[to[i]]=x,Q[ta++]=to[i];
    }
}
inline int read() {
    char ch=getchar(); int num=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch^'0'),ch=getchar();
    return num;
}
inline void update(int x) {
    if(!fa[x]) return ;
    for(register int i=head[x];i;i=from[i])
        if(f[x]-1>f[to[i]]) {
            f[to[i]]=f[x]-1;
            update(to[i]);
        }
}
int main() {
    n=read(),k=read(),t=read();
    for(register int i=1;i<n;++i) {
        int u=read(),v=read();
        add(u,v); add(v,u);
    }
    bfs(); memset(f,-1,sizeof(f));
    for(register int i=n;i;--i) {
        if(f[Q[i]]==-1) {
            ++ans; int x=Q[i];
            for(register int j=k;j;--j) x=fa[x];
            f[x]=k; update(x);
        }
    }
    printf("%d\n",ans);
    return 0;
}