P8399 [CCC2022 S5] Good Influencers 做题记录

llingy · 2023-12-02 22:41:01 · 题解

题意简述

给定一棵 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;
}