bzoj1304

树形dp

题目是要求最深的颜色

先开始觉得设dp[i][0/1/2]表示这个点的状态，然后发现没办法保证该点是最深的点，且dp状态没有实际意义，其实dp[i][0/1]表示当前i的子树颜色为c^1的叶子结点都已经染好了，现在颜色为c的还没染好，注意当前i节点还没有染色，那么dp[i][0]=min(dp[j][0],dp[j][1]+1),表示j为根的子树白色还没染好，黑色染好了，那么当前到i还是没染好，也就不用把i节点染色，继续保持没有染好的状态，d[j][1]+1表示j的子树中0染好了，1没染好，那么现在变成1已经染好而0没有染好，所以必须染一个1，那么操作数量+1，也就把j子树中的1染好了

最后就是min(dp[root][0],dp[root][1])+1,+1是因为dp状态表示当前树中还有一种颜色没染好，所以必须染一次，+1，这里节点没有染色是由dp[i][0]=dp[j][0],表示当前i节点暂时不染色。保证子树中一种颜色染好而另一种颜色没有染好是由dp初值保证的，叶子结点dp[i][c]=0,dp[i][c^1]=inf,表示不存在的颜色不存在没有染好的情况。

#include<bits/stdc++.h>

using namespace std;

const int N = ;

int n, m;

int dp[N][], c[N];

vector<int> G[N];

void dfs(int u, int last)

{

    if(u <= m)

    {

        dp[u][c[u] ^ ] =  << ;

        return;

    }

    for(int i = ; i < G[u].size(); ++i)

    {

        int v = G[u][i];

        if(v == last) continue;

        dfs(v, u);

        dp[u][] += min(dp[v][], dp[v][] + );

        dp[u][] += min(dp[v][], dp[v][] + );

    }

}

int main()

{

    scanf("%d%d", &n, &m);

    for(int i = ; i <= m; ++i) scanf("%d", &c[i]);

    for(int i = ; i < n; ++i)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs(n, );

    printf("%d\n", min(dp[n][], dp[n][]) + );

    return ;

}

巴特西

bzoj1304

最新文章

热门文章