LuoGu P2279 消防局的设立

题目描述

2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地。起初为了节约材料，人类只修建了n-1条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话，我们称基地A到基地B的距离为d。

由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过2的基地的火灾。

你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。

输入文件的第一行为n （n<=1000），表示火星上基地的数目。接下来的n-1行每行有一个正整数，其中文件第i行的正整数为a[i]，表示从编号为i的基地到编号为a[i]的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有a[i]<i。

输出文件仅有一个正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。

本题是 POJ2152 消防站 弱化版

以POJ2152 思路撰写

参考
国家集训队2006年论文《一张一弛，解题之道——“约制、放宽”方法在解题中的应用》 ————广东省中山纪念中学 陈启峰

思路与分析：

通过读题可以看出 本题需要在部分节点建造最少数量的消防站以覆盖整张图
每个节点的消防站可以覆盖距离不大于2的节点（可以为任意值）

当做1个消防站修建代价为1

用F[i][j]表示以i为根的子树被j建筑的消防站所需要的最小的代价
(j可能在字数内也可能在子树外)
F[i][j]的特性：
– 以i为根的子树里修建一些消防站；

• 在结点j必须修建一个消防站；

• 以i为根的子树内的每个结点在不超过距离 的前提下,选择一个在子树内或结点j上的消防站作为负责站；

• 结点i必须选择结点 上的消防站作为负责站；

用Best[i]表示以i节点被子树内的节点覆盖的最小代价

通过分析，我们得出:

对于Best[i] 因为要覆盖自己子树的所有节点

又因为在计算F[i][j] 计算了以i为根的子树的最优点

所以Best[i]=min{F[i][j]},j是i的儿子;

现在考虑如何通过转移方程来维护Best和F的特性
对于F[i][j] 有三种情况

• j 在以i为节点子树外
• j ==i
• j 在以i为节点子树内

对于 j 在以i为节点子树外的情况

如果Dis(i,j)>D（D表示限制距离，本题为2）

表示j覆盖不到i点，所以覆盖不到以i为子树上的任何点

所以F[i][j]是非法状态，设置为∞，使得以后不会从此状态转移

如果Dis(i,j)<=D

那么此时j可以覆盖到i点，但能否覆盖到以i为子树的所有点就不一定了

在这里插入一句，我们树形DP一般采用后序遍历，所以对父亲执行过的操作，对他的儿子自然是执行过了

着手分析i的儿子k

如果某儿子F[k][j] != ∞ ，说明 k 在j的距离内，并且F[k][j]保存的是j点覆盖k点，以及以k为子树所有点都被覆盖的情况

k有两种情况
1. 被自己子树内的节点覆盖，最小代价为Best[k]
2. 被j覆盖，最小代价为F[k][j]

所以F[i][j]如果要覆盖自己的儿子j，必有此两种情况

所以F[i][j]+=min(Best[k],F[k][j])

此处有一个递归定义的过程，需要反复揣摩

对于 j==i 的情况

与上文类似，不过要在i节点修建加油站，所以F[i][j]+=1;

对于j在i的子树内的情况

j在i的子树内，那么j必有一个祖先k是i的直接儿子，也可能j就是i的直接儿子

因为对于i节点，必须被j覆盖，所以k节点也可以被j覆盖

对于其他节点，被j覆盖的最优自然是min(Best[k],F[k][j])

所以F[i][j]+=min(Best[p],F[p][j]) p表示i的儿子且p!=k

F[i][j]+=F[k][j];

对于两点的距离，我们用LCA提前维护出来就好

Dis(i,j)=D[i]+D[j]-2*D[LCA(i,j)]

对于验证j点是不是在i的子树内 只用判断LCA(i,j)是否等于i即可

本题情况复杂，状态设置巧妙，转移需要考虑多种情况

验证起来比较麻烦，可能出现对状态的合理性表示怀疑的情况，即怀疑为什么是这个状态，感觉不对的情况。

具体证明及其详细过程可以阅读陈启峰的解题报告

我的代码在文末

代码：

#include<bits/stdc++.h>//使用复杂方法解决简单问题 
#define INF 99999999
int last[2000],cnt,n;
int best[1010],log2n;
int f[1010][1010],d[1010],v[1010],F[1010][30];
int lca[1010][1010];
int dis[1010][1010];
std::vector<int> vec[1010];
struct edge{
    int to,next;
}e[2000];
inline void add(int x,int y){
    cnt++;e[cnt].to=y;e[cnt].next=last[x],last[x]=cnt;
}
inline int dfs_first(int x,int fa){
    v[x]=1;
    d[x]=d[fa]+1;
    F[x][0]=fa;
    for(int i=last[x];i;i=e[i].next){
        if(v[e[i].to]) continue;
        dfs_first(e[i].to,x) ;
    } 
}
inline void BZ(){
    for(int i=1;i<=log2n;++i)
        for(int j=1;j<=n;++j){
             if(d[j]>=(1<<i)){
                F[j][i]=F[F[j][i-1]][i-1];
             }
        }
}
inline int LCA(int x,int y){
    if(d[x]<d[y]) std::swap(x,y);
    for(int i=log2n;i>=0;--i){
        if(d[F[x][i]]>=d[y])
            x=F[x][i];
    }
    if(x==y) return x;
    for(int i=log2n;i>=0;--i){
        if(F[x][i]!=F[y][i])
            x=F[x][i],y=F[x][i];
    }
    return F[x][0];
}
inline void dfs(int x){
    v[x]=1;
    for(int i=last[x];i;i=e[i].next){
        if(v[e[i].to]) continue;
        dfs(e[i].to);

    }
        for(int j=1;j<=n;++j){
            if(dis[x][j]>2) f[x][j]=INF;
            if(dis[x][j]<=2){
                if(lca[x][j]!=x&&x!=j){
                    for(int i=last[x];i;i=e[i].next){
                        if(lca[x][e[i].to]==x&&e[i].to!=x)
                        f[x][j]+=std::min(best[e[i].to],f[e[i].to][j]);
                    }
                }
                if(lca[x][j]==x){
                    if(f[x][j]>=INF) 
                        f[x][j]=0;
                    if(x==j) {
                        f[x][j]+=1;
                    for(int i=last[x];i;i=e[i].next){
                        if(lca[e[i].to][x]!=x) continue;
                        f[x][j]+=std::min(best[e[i].to],f[e[i].to][j])  ;
                    }
                        continue; 
                    }
                    for(int i=last[x];i;i=e[i].next){//child
                        if(lca[e[i].to][j]==e[i].to&&lca[e[i].to][x]==x){
                            int k=e[i].to;
                            f[x][j]+=f[k][j];
                            for(int iii=last[x];iii;iii=e[iii].next){
                                if(e[iii].to==k) continue;
                                if(lca[e[iii].to][x]!=x) continue; 
                                f[x][j]+=std::min(best[e[iii].to],f[e[iii].to][j]);
                            }
                            break;//只执行一次，找j的祖先且是x的儿子 
                        }
                    }
                } 

            }
        }
        for(int i=1;i<=n;++i){
            if(lca[i][x]==x)
                best[x]=std::min(best[x],f[x][i]);
        }
    }
int main (){
    scanf("%d",&n);
    for(int i=2;i<=n;++i){
        int x;
        scanf("%d",&x);
        add(x,i),add(i,x);
    }
    log2n=log(n*1.0)/log(2.0)+0.5;
    dfs_first(1,0);
    BZ();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
        best[i]=INF;//f[i][j]=INF;
    }
    memset(v,0,sizeof(v));
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j){
            lca[i][j]=LCA(i,j); 
            lca[j][i]=lca[i][j];
            dis[i][j]=d[i]+d[j]-d[lca[i][j]]*2;
            dis[j][i]=dis[i][j];
        }

    dfs(1);
    printf("%d",best[1]);
}