叶子的染色

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2254 字
给定各叶子要求的最终着色颜色，给节点黑白着色
一本通
练习
正文

/*
原题：叶子的染色（一本通 5.2 练习4）
题意：给定各叶子要求的最终着色颜色，给节点黑白着色使每条根到叶路径都含一个有色点且其最后有色点颜色符合，求最少着色数。
思路：选度数>1 的节点作根。五态树形 DP：0 黑、1 白、2 未涂且需祖先黑、3 未涂且需祖先白、4 未涂且已自满足。叶子按固定色取初值，根不可用 2/3。
复杂度：O(m) 时间，O(m) 空间。
易错点：叶子颜色是“路径最后有色点”的颜色而非叶子必须涂；合并儿子时黑/白要求冲突则不可行；必须根在内部节点。
*/
#include <bits/stdc++.h>
using namespace std;
const int M=10005;
const int INF=1e9;
int m,n;
vector<int> g[M];
int col[M];
int dp[M][5];
void dfs(int u,int fa){
    vector<int> ch;
    for(int v:g[u])
        if(v!=fa)ch.push_back(v);
    if(u>=1&&u<=n&&ch.empty()){
        dp[u][0]=(col[u]==0?1:INF);
        dp[u][1]=(col[u]==1?1:INF);
        dp[u][2]=(col[u]==0?0:INF);
        dp[u][3]=(col[u]==1?0:INF);
        dp[u][4]=INF;
        return;
    }
    for(int v:ch)dfs(v,u);
    dp[u][0]=1;
    dp[u][1]=1;
    for(int v:ch){
        dp[u][0]+=min({dp[v][0],dp[v][1],dp[v][2],dp[v][4]});
        dp[u][1]+=min({dp[v][0],dp[v][1],dp[v][3],dp[v][4]});
    }
    long long bsat=0,bblk=INF,bwht=INF;
    for(int v:ch){
        long long sat=min({(long long)dp[v][0],(long long)dp[v][1],(long long)dp[v][4]});
        long long blk=dp[v][2];
        long long wht=dp[v][3];
        long long nbsat=INF,nbblk=INF,nbwht=INF;
        if(bsat<INF){
            nbsat=min(nbsat,bsat+sat);
            nbblk=min(nbblk,bsat+blk);
            nbwht=min(nbwht,bsat+wht);
        }
        if(bblk<INF){
            nbsat=min(nbsat,bblk+sat);
            nbblk=min(nbblk,bblk+blk);
        }
        if(bwht<INF){
            nbwht=min(nbwht,bwht+sat);
            nbwht=min(nbwht,bwht+wht);
        }
        bsat=nbsat;
        bblk=nbblk;
        bwht=nbwht;
    }
    dp[u][4]=bsat;
    dp[u][2]=bblk;
    dp[u][3]=bwht;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>m>>n;
    for(int i=1;i<=n;i++)cin>>col[i];
    for(int i=1;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int root=1;
    for(int i=1;i<=m;i++)
        if((int)g[i].size()>1){
            root=i;
            break;
        }
    if(g[root].size()<=1){
        if(m==1){cout<<1<<"\n";return 0;}
        if(m==2){cout<<(col[1]==col[2]?1:2)<<"\n";return 0;}
    }
    dfs(root,-1);
    cout<<min({dp[root][0],dp[root][1],dp[root][4]})<<"\n";
    return 0;
}
叶子的染色

正文

一本通·提高篇的其它内容
