AT_arc097_d [ARC097F] Monochrome Cat 题解

· · 题解

模拟赛 T3 遇到，糖糖 DP。

思路分析：

考虑暴力的 O(n^2) DP。定义 f_u 表示遍历以 u 为根的子树然后回到 fa_u，g_u 表示遍历后就不回来了（在子树内结束遍历），t_u 表示 u 儿子个数，有如下转移：

f_u=\sum_{(u,v)\in E} f_v+(t_u+[c_u=W]+1)\bmod 2+2 g_u=\sum_{(u,v)\in E} f_v-\max_{(u,v)\in E}(f_v-g_v)+(\max(0,t_u-1)+[c_u=W]+1)\bmod 2 +1

发现有点问题，如果一颗子树内没有白点我们是可以不遍历的，于是定义 h_u 表示以 u 为根的子树中有多少给白点，如果 h_v=0 就不转移。

发现还有点问题，根节点在一开始不会被到达，所以直接特殊处理根节点:

f_{rt}=\sum_{({rt},v)\in E} f_v+(t_{rt}+[c_{rt}=W])\bmod 2 g_{rt}=\sum_{({rt},v)\in E} f_v-\max_{({rt},v)\in E}(f_v-g_v)+(\max(0,t_{rt}-1)+[c_{rt}=W])\bmod 2

还有一种办法是预先修改一次根的颜色（抵消我们认为其被到达的修改），然后求答案时把边的移动删掉。

发现上式结构还是相对简单的，直接换根即可，代码如下。

AC Code:

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e5+10;
int n,f[N],g[N],h[N],c[N],t[N],s[N],m2[N],m1[N],ans;
vector<int>e[N];
void dfs1(int u,int fa,int rt){
    h[u]=c[u];
    t[u]=0,s[u]=0,m2[u]=0,m1[u]=0;
    for(int v:e[u])if(v!=fa){
        dfs1(v,u,rt),h[u]+=h[v];if(h[v]==0)continue;
        t[u]++,s[u]+=f[v],m2[u]=max(m2[u],f[v]-g[v]);
        if(m2[u]>m1[u])swap(m2[u],m1[u]);
    }
    if(u==rt)
        f[u]=s[u]+((t[u]+c[u])&1),
        g[u]=s[u]-m1[u]+((t[u]-(t[u]>0)+c[u])&1);
    else
        f[u]=s[u]+((t[u]+c[u]+1)&1)+2,
        g[u]=s[u]-m1[u]+((t[u]-(t[u]>0)+c[u]+1)&1)+1;
}
void dfs2(int u,int fa){
    ans=min({ans,f[u],g[u]});
    for(int v:e[u])if(v!=fa){
        int fu=f[u],gu=g[u],hu=h[u],tu=t[u],su=s[u],m2u=m2[u],m1u=m1[u];
        int fv=f[v],gv=g[v],hv=h[v],tv=t[v],sv=s[v],m2v=m2[v],m1v=m1[v];
        if(h[v]>0){
            t[u]--,s[u]-=f[v];
            if(f[v]-g[v]==m1[u])swap(m1[u],m2[u]);
        }
        h[u]-=h[v],h[v]+=h[u];
        f[u]=s[u]+((t[u]+c[u]+1)&1)+2,
        g[u]=s[u]-m1[u]+((t[u]-(t[u]>0)+c[u]+1)&1)+1;
        if(h[u]>0){
            t[v]++,s[v]+=f[u],m2[v]=max(m2[v],f[u]-g[u]);
            if(m2[v]>m1[v])swap(m2[v],m1[v]);
        }
        f[v]=s[v]+((t[v]+c[v])&1),
        g[v]=s[v]-m1[v]+((t[v]-(t[v]>0)+c[v])&1);
        dfs2(v,u);
        f[u]=fu,g[u]=gu,h[u]=hu,t[u]=tu,s[u]=su,m2[u]=m2u,m1[u]=m1u;
        f[v]=fv,g[v]=gv,h[v]=hv,t[v]=tv,s[v]=sv,m2[v]=m2v,m1[v]=m1v;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1,u,v;i<n;i++)
        cin>>u>>v,e[u].pb(v),e[v].pb(u);
    string s;cin>>s;s=' '+s;
    for(int i=1;i<=n;i++)
        c[i]=(s[i]=='W');
    dfs1(1,0,1);
    ans=n*3;
    dfs2(1,0);
    cout<<ans;
    return 0;
}

完结撒花！！！