【题解】Luogu P3942 将军令贪心

- 日理万妓 2023-08-17 16:49 87阅读 0赞

f\[x\]\[0\] 表示最近控制驿站的距离

f\[x\]\[1\]表示最远不能控制的驿站距离

当f\[x\]\[0\]+f\[x\]\[1\]≤k是说明能被控制，但没有贡献

当f\[x\]\[1\]=k时，x必须被控制，这时已经到达能控制点的最远距离，如果再向上，x就无法被控制

正确性：如果x可以向上移动，并且仍然能控制x移动前能控制的点，就把x向上移动，这样不会变差的

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4 #define ll long long
     5 const int maxn=1e5+10;
     6 const int inf=1e9+7;
     7 inline int read(){
     8     int x=0,f=1;
     9     char c=getchar();
    10     while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
    11     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
    12     return x*f;
    13 }
    14 int n,k,t,ans;
    15 struct edge{
    16     int nxt,to;
    17 }e[maxn*2];
    18 int head[maxn],cnt,f[maxn][2];
    19 inline void add(int from,int to){
    20     e[++cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt;
    21 }
    22 void dfs(int x,int fa){
    23     f[x][0]=inf;f[x][1]=0;
    24     for(int i=head[x];i;i=e[i].nxt){
    25         int y=e[i].to;
    26         if(y==fa)continue;
    27         dfs(y,x);
    28         if(~f[y][1]){
    29             f[x][1]=max(f[x][1],f[y][1]+1);
    30         }
    31         f[x][0]=min(f[x][0],f[y][0]+1);
    32     }
    33     if(f[x][1]==k){
    34         ans++;
    35         f[x][0]=0;f[x][1]=-1;
    36     }
    37     if(f[x][1]+f[x][0]<=k)f[x][1]=-1;
    38 }
    39 int main(){
    40     n=read();k=read();t=read();
    41     for(int i=1;i<n;i++){
    42         int x,y;x=read();y=read();
    43         add(x,y);add(y,x);
    44     }
    45     dfs(1,0);
    46     if(~f[1][1])ans++;
    47     printf("%d",ans);
    48     return 0;
    49 }
    50 }
    51 signed main(){
    52   gengyf::main();
    53   return 0;
    54 }

转载于:https://www.cnblogs.com/gengyf/p/11598958.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/798a881407f3435b88d5b779d5410ed4.png