P3267题解

0 前言

ylq：“你们完全理解了这道题，那树形dp也就都会了。”

我完全同意这句话。

其实是因为太菜了做了很久这道题才想明白是怎么搞的

1 题意

给你一颗 $n$ 个点的树，还有 $m$ 个关键点需要覆盖，你需要选择若干个点，使得所有关键点距离你选择的点中至少一个距离不超过 $d$，选择一个点的代价是 $c_i$，需要你最小化这个代价。

2 思路

其实我觉得，这道dp有价值的地方就在于它从状态设计，到转移，到最后的代码实现都有一些难点或者是细节。非常值得反复推敲。

其实就是难，我也不知道为什么降蓝了，你谷评分机制发力了

首先，假定你已经看出来了这是一道树形dp，那么开始想它的状态设计。如果做过类似有关于树上点对距离的树形dp题目应该可以想到，我们可以用一维记录有关距离的信息。

于是我们可以想到一个状态：$f_{u,k}$ 表示点 $u$ 的子树之中的点已经被完全覆盖，而且这个子树还可以从 $u$ 向外覆盖 $k$ 层。

于是你觉得自己马上能设计出来转移方程的时候，你发现了一件事情：一个子树中的点可以对另一个子树中的点产生贡献。因此转移可能并不是是简单的父子间转移。

到了这一步，也许就已经卡住了。那么下一步该怎么做呢？

这时候，也许会有一个奇妙的想法冒出来：我们最终并不关心子节点具体的贡献，因此子节点之间的贡献可以在父节点处合并计算。（子树dp）

因此，我们考虑如下情况：

图画的好烂

黑色的子树是前面已经遍历过的子树，我们已经从前面的子树之中合并出了 $f_{u,k}$，现在遍历了 $v$ 节点。现在显然有三种情况可以合并出 $f_{u,k}$：

• 前面的子树都已经覆盖完了，$v$ 子树也已经覆盖完了。

• 前面的子树都已经覆盖完了，$v$ 子树还没有覆盖完。

• 前面的子树还没有覆盖完，$v$ 子树覆盖完了。

显然，第一种情况是平凡的，可以直接合并$f_{v,k+1}$ 的信息。然后我们想，想要合并后两种信息，我们如何处理没有覆盖完的情况呢？

我们用 $g_{u,k}$ 表示在 $u$ 的子树内，距离 $u$ 点 $k$ 深度及以下的点都已经被覆盖，以上的点没有完全被覆盖的最小代价。

形象的说：

我们以第三种情况为例子。如图，绿色子树代表前面我们已经遍历过的子树，实色部分表示 $k$ 层以下已经覆盖完，空白部分表示 $k$ 层以上没有完全被覆盖。红色子树也就是 $v$ 子树，表示 $v$ 子树已经覆盖完，黑色倒三角就表示 $v$ 子树还能向外再覆盖 $j$ 层。

那么显然的，我们经过 $u$ 点，可以将 $g_{u,k+1}+f_{v,k+1}$ 这一部分合并进贡献。

第二种情况同理。可以将 $g_{v,k}+f_{u,k}$ 这一部分合并进贡献。因此这时候我们有了一个转移方程：

$$f_{u,k}=\sum_{v\in u} \min(f_{u,k}+f_{v,k+1},g_{u,k+1}+f_{v,k+1},g_{v,k}+f_{u,k})$$

到这里本题已经做完一大半了。

其次，我们想一下 $g$ 如何转移。

显然的，向上转移一层一定是不选当前节点，因此累加子节点即可

$$g_{u,k}=\sum_{v\in u} g_{v,k-1}$$

然后，为了保证答案正确性，我们考虑从 $f_{u,k}$ 到 $f_{u,k-1}$ 是对外贡献缩小了一层，感性理解答案应该不增。因此我们应该对每一个 $f_{u} $ 做后缀最小值，即：

$$f_{u,k}=\min(f_{u,k},f_{u,k+1})$$

再考虑 $g$，考虑从 $g_{u,k-1}$ 到 $g_{u,k}$ 是在子树中少向上覆盖了一层，因此感性理解答案应该不增。所以同理：

$$g_{u,k}=\min(g_{u,k-1},g_{u,k})$$

最后，我们考虑初始情况。

考虑 $k=0$ 的情况，那么 $f_{u,0}$ 和 $g_{u,0}$ 就可以看作是选一个点的代价。那么考虑所有关键点首先要被选上，所以对于所有关键点都应有 $f_{u,0}=g_{u,0}=c_u$ 。

其次考虑 $k\neq 0$ 的情况，我们考虑向外的贡献，因为向下的贡献可以由子树合并过来。选择一个点向外覆盖 $d$ 的距离，所以对于 $1\leq i\leq d$，都应有 $f_{u,i}=c_u$。

对于所有另外的情况，因为我们的答案是求最小值，因此全部其他的 $d\leq i$， $f_{u,i}=+\infin$ 。

以上就是本题大体上的全部思路。

3 实现

本题的实现有一些细节需要注意。

在遍历合并子树信息的时候，需要注意转移的顺序。

应该首先初始化边界条件。然后在到节点 $u$ 开始合并子树信息时，应该先用第一个方程转移，然后更新 $f$ 的后缀最小值，最后进行 $g$ 数组的更新。

具体的部分核心代码如下：

vector<int> g[N];
int n,m,d;
int c[N],b[N];
int f[N][25],dp[N][25];
void solve(int x,int fa){
    if(b[x])f[x][0]=dp[x][0]=c[x];
    else f[x][0]=dp[x][0]=0;
    for(int i=1;i<=d;++i){f[x][i]=c[x];}
    for(auto &i:g[x]){
        if(i==fa)continue;
        solve(i,x);
    }
    for(auto &i:g[x]){ 
        if(i==fa)continue;
        for(int j=d;j>=0;--j){
            f[x][j]=min(min(f[x][j]+dp[i][j],f[i][j+1]+dp[x][j+1]),f[x][j]+f[i][j+1]);
        }
        for(int j=d;j>=0;--j){
            f[x][j]=min(f[x][j],f[x][j+1]);
        }
        dp[x][0]=f[x][0];//注意此处需要更新g
        for(int j=1;j<=d+1;++j){
            dp[x][j]+=dp[i][j-1];
        }
        for(int j=1;j<=d+1;++j){
            dp[x][j]=min(dp[x][j],dp[x][j-1]);
        }
    }
}
signed main(){
    n=read();d=read();
    for(int i=1;i<=n;++i)c[i]=read();
    m=read();
    for(int i=1;i<=m;++i)b[read()]=1;
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        g[u].push_back(v);
        g[v].push_back(u);        
    }
    memset(f,0x3f,sizeof f);
    solve(1,0);
    printf("%lld",f[1][0]);
    return 0;
}

4 时间复杂度分析

$dfs$ 的时间复杂度为 $O(n)$，中间循环第二维 $d$，总的时间复杂度 $O(nd)$。

5 待补

一个十四岁的少女决定去死。

To be continue…