P3267 JLOI2016/SHOI2016 侦察守卫
互相赋值的双 dp
思路
设 \(f[u][i]\) 表示包括 \(u\) 子树内所有关键点都被覆盖（包括 \(u\)），且至少还可以向 \(u\) 的父亲方向覆盖 \(i\) 层的最小代价。
设 \(g[u][i]\) 表示向下距离大于等于 \(i\) 的点全部被覆盖，剩下距离小于 \(i\) 的点随意的最小代价。
设 \(v\) 是 \(u\) 的儿子，有转移：
\[f[u][i]=\min(f[u][i]+g[v][i],g[u][i+1]+f[v][i+1])\\ g[u][i]=\sum_{v\in u.sons} g[v][i-1] \]\(f\) 的转移可以理解为自己覆盖，和儿子覆盖两种情况。
根据 \(f\) 和 \(g\) 的定义还有以下转移：
\[f[u][i]=\min(f[u][i],f[u][i+1])\\ g[u][i]=\min(g[u][i],g[u][i-1]) \]有了方程之后还需要区分关键点和普通点的初始值。
若为关键点 \(f[u][0]=w[u]\)。
若为普通点 \(f[u][0]=0\)。
这里初始值是只包括自己一个节点，需要和儿子进行合并得到最终答案。
又 \(f[u][i]=w[u]\)，满足 \(1\leq i\leq d\)。
当然了，我们在转移时先转移 \(f\) 再转移 \(g\)，因为 \(f\) 转移时 \(g\) 的定义是不包括当前的儿子的。
对于 \(g[u][0]\) 每次需要附初值 \(g[u][0]=f[u][0]\)。
转移顺序详见代码。
CODE
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
struct Edge
{
int tot;
int head[maxn];
struct edgenode{int to,nxt;}edge[maxn*2];
inline void add(int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
}T;
int n,d,m;
int f[maxn][50],g[maxn][50],w[maxn];
bool vis[maxn];
inline void dfs(int u,int fa)
{
if(vis[u]) g[u][0]=f[u][0]=w[u];
else g[u][0]=f[u][0]=0;
for(int i=1;i<=d;i++) f[u][i]=w[u];
for(int i=T.head[u];i;i=T.edge[i].nxt)
{
int v=T.edge[i].to;
if(v==fa) continue;
dfs(v,u);
}
for(int i=T.head[u];i;i=T.edge[i].nxt)
{
int v=T.edge[i].to;
if(v==fa) continue;
for(int j=d;~j;j--) f[u][j]=min(min(f[u][j]+g[v][j],g[u][j+1]+f[v][j+1]),f[u][j]+f[v][j+1]);
for(int j=d;~j;j--) f[u][j]=min(f[u][j+1],f[u][j]);
g[u][0]=f[u][0];
for(int j=1;j<=d+1;j++) g[u][j]+=g[v][j-1];
for(int j=1;j<=d+1;j++) g[u][j]=min(g[u][j],g[u][j-1]);
}
for(int j=d;~j;j--) f[u][j]=min(f[u][j+1],f[u][j]);
for(int j=1;j<=d+1;j++) g[u][j]=min(g[u][j],g[u][j-1]);
}
int main()
{
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
scanf("%d",&m);
for(int i=1,x;i<=m;i++) scanf("%d",&x),vis[x]=true;
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
T.add(x,y),T.add(y,x);
}
memset(f,0x3f,sizeof(f));
dfs(1,0);
int ans=1e9;
for(int i=0;i<=d;i++)
ans=min(ans,f[1][i]);
printf("%d",ans);
}