P8399 [CCC2022 S5] Good Influencers 做题记录

题意简述

给定一棵 $n$ 个点的树，点有蓝色和白色两种颜色，每次选择一个蓝点 $u$ 并将所有距离为 $1$ 的点染成蓝色，代价为该点的点权 $w_u$，求将树全变为蓝色的最小代价。$n\le 2\times 10^5$。

思路

树 DP。

每个点要么被父亲染成蓝色，要么被儿子染成蓝色。设 $f_{u,0/1/2/3}$ 为对于 $u$ 子树内所有节点都被染成蓝色，$u$ 被选择，父亲需要被选择 / $u$ 不被选择，父亲需要被选择 / $u$ 被选择，父亲不需要被选择 / $u$ 不被选择，父亲不需要被选择。

在 $u$ 下方加入一个儿子 $v$。则有转移：

• 对于 $f_{u,0}$ 的转移，$u$ 被选择，则对 $v$ 不做要求，任意状态均可转移。$f_{u,0}\gets f_{u,0}+\min\{f_{v,0},f_{v,1},f_{v,2},f_{v,3}\}$。
• 对于 $f_{u,1}$ 的转移，$u$ 不被选择，则需要 $v$ 不依赖 $u$ 染成蓝色。$f_{u,1}\gets f_{u,1}+\min\{f_{v,2},f_{v,3}\}$。
• 对于 $f_{u,2}$ 的转移，$u$ 被选择，则对 $v$ 不做要求。同时应当考虑 $v$ 将 $u$ 染色的情况，此时 $v$ 应当满足被选择且不依赖父亲染色。$f_{u,2}\gets\min\{\min\{f_{v,0},f_{v,1},f_{v,2},f_{v,3}\}+f_{u,2},f_{u,0}+f_{v,2}\}$。
• 对于 $f_{u,3}$ 的转移，$u$ 不被选择，则需要 $v$ 不依赖 $u$ 染成蓝色。应当考虑 $v$ 将 $u$ 染色的情况，$v$ 同样应当满足被选择且不依赖父亲染色。$f_{u,3}\gets\min\{\min\{f_{v,2},f_{v,3}\}+f_{u,3},f_{u,1}+f_{v,2}\}$。

初始值 $f_{u,0}\gets w_u,f_{u,1}\gets 0$。如果 $u$ 一开始为蓝色，则 $f_{u,2}\gets w_u,f_{u,3}\gets 0$。否则 $f_{u,2}\gets +\infty,f_{u,3}\gets +\infty$。

Code

转移时应当注意顺序，不过更好的方式是使用临时数组来存储原来的 DP 值。

constexpr int N=2e5+5,inf=1e9;using ll=long long;
struct edge{int to,nxt;}e[N<<1];
int head[N],cnt=0;char s[N];
inline void add(int u,int v){e[++cnt]=(edge){v,head[u]};head[u]=cnt;}
ll f[N][4],w[N],g[4];bool col[N];
inline void dfs(int u,int fa)
{
    f[u][0]=w[u];f[u][1]=0;f[u][2]=f[u][3]=inf;
    if(col[u]) f[u][2]=w[u],f[u][3]=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;if(v==fa) continue;
        dfs(v,u);memcpy(g,f[u],sizeof(g));
        f[u][0]=min({f[v][0],f[v][1],f[v][2],f[v][3]})+g[0];
        f[u][1]=min(f[v][2],f[v][3])+g[1];
        f[u][2]=min(f[v][2]+g[0],g[2]+min({f[v][0],f[v][1],f[v][2],f[v][3]}));
        f[u][3]=min(f[v][2]+g[1],g[3]+min(f[v][2],f[v][3]));
    }
}
inline void work()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n;cin>>n;for(int i=1,u,v;i<n;i++) cin>>u>>v,add(u,v),add(v,u);
    cin>>(s+1);for(int i=1;i<=n;i++) col[i]=(s[i]=='Y');
    for(int i=1;i<=n;i++) cin>>w[i];
    dfs(1,0);cout<<min(f[1][2],f[1][3])<<endl;
}