题解 P3942 【将军令】无预处理O(n)

· · 题解

大佬们是不是想难了。。这道题是考试20分钟打的，当时我还想，是不是想简单了

做这道题后建议做这道 P3523 [POI2011]DYN-Dynamite

贪心做法

我们每个节点记录两个值，f[x][0] 表示x到最近控制驿站的距离，f[x][1]表示x到最远没被控制点的距离

当f[x][0]+f[x][1]<=k时说明这个点能被控制，不能对上面的点贡献

当f[x][1]=k时，点x必须被控制，把f[x][0]改成0,f[x][1]改成-1,++ans,因为这时已经到达能控制点的最远距离，如果再向上，x就无法被控制，树上两点间的路径是唯一的

特判根节点是否能被控制，不能则++ans;

细节：稍微模拟可知统计答案时，f[x][0]和f[x][1]只有一个有用，当f[x][0]不能控制f[X][1]时，f[x][0]就失去作用了

贪心思路证明：

考虑被控制节点x，如果x可以向上移动一，并且仍然能控制x移动前能控制的点，就把x向上移动，显然，这样做是不会使答案变差的。

我们不知道x向上移动后能控制多少点，但显然，x有可能控制更多的点，这时把x移动到不能移动为止，x就成为了最优答案。

code 150ms 开O(2)变慢了，不造为啥

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cmath>
using namespace std;
namespace OI{
    #define rg register
    template<class T>
    inline void read(T &x){
        x=0;
        static char ch;
        static int f;
        ch=getchar();
        f=0;
        while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        x=f?-x:x;
    }
    const int N=200010;
    int head[N],nxt[N<<1],ver[N<<1],tot;
    int n,k,t,ans;
    //0 最近被控制点
    //1 最远没控制点
    int f[N][2];
    inline void add(int x,int y){
        ver[++tot]=y;
        nxt[tot]=head[x];
        head[x]=tot;
    }
    const int inf=0x3f3f3f3f;
    void dfs(int x,int fa){
        f[x][0]=inf;//初始
        f[x][1]=0;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            if(y==fa) continue;
            dfs(y,x);
            if(~f[y][1]) f[x][1]=max(f[x][1],f[y][1]+1);//这里如果下面的点被控制，就不考虑（因为如过继续考虑会多算贡献）
            f[x][0]=min(f[x][0],f[y][0]+1);
        }
        if(f[x][1]==k){//加控制点
            ++ans;
            f[x][0]=0;
            f[x][1]=-1;
        }
        if(f[x][1]+f[x][0]<=k) f[x][1]=-1;//被控制标记
    }
    void main(){
        read(n),read(k),read(t);
        for(int x,y,i=1;i<n;++i){
            read(x),read(y);
            add(x,y);
            add(y,x);
        }
        dfs(1,0);
        if(~f[1][1]) ++ans;//特判根节点
        cout<<ans<<endl;
    }
}
int main(){OI::main();return 0;}

希望能过QAQ