Luogu P3942 将军令

题目

维护每个点子树中最深的没有被覆盖的点（仅计算这条链上的关键点）的距离。

若\(u\)为关键点，则\(d_u=-k-1\)。

记录\(mx=\max\limits_{v\in son_u}d_v+1,min=\min\limits_{v\in son_u}d_v+1\)。

如果\(mx+mn<0\)，那么说明这个点的子树已经全被覆盖了，那么\(d_u=mn\)。（这里是考虑到别的链上的关键点覆盖了这个点的子树）

否则这个点的子树没有全被覆盖，最深的没有被覆盖的点的深度依旧是\(mx\)，\(d_u=mx\)。

如果\(d_u\ge k\)，那么我们就在这个点设置一个关键点。

最后如果\(d_1\ge0\)就要继续答案加一。

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

const int N=1e5+1;

int n,k,ans,d[N];

vector<int>E[N];

int read(){int x;scanf("%d",&x);return x;}

void max(int &a,int b){a=a>b? a:b;}

void min(int &a,int b){a=a<b? a:b;}

void dfs(int u,int fa)

{

    int mx=0,mn=k+1;

    for(int v:E[u]) if(v^fa) dfs(v,u),max(mx,d[v]+1),min(mn,d[v]+1);

    if((d[u]=(mx+mn<0? mn:mx))>=k) d[u]=-k-1,++ans;

}

int main()

{

    n=read(),k=read(),read();int i,u,v;

    for(i=1;i<n;++i) u=read(),v=read(),E[u].pb(v),E[v].pb(u);

    if(dfs(1,0),d[1]>=0) ++ans;

    return !printf("%d",ans);

}

巴特西

Luogu P3942 将军令

最新文章

热门文章