题解 P4084 【[USACO17DEC]Barn Painting】

· · 题解

又是一道树形dp的题

这道题和P1352 没有上司的舞会还是挺像的，这个可能更加复杂一些。不过我觉得难度可能都还属于树形dp的入门题。

树形dp本质上来说就是dfs一遍树然后进行递推，这道题中可以开个二维的数组dp[i][j]表示编号为i的点涂上j颜色的方案数。

显然每个点的方案数和它的子树是有关的，所以我们要先遍历到叶子节点然后一步步往回推。

由于相邻的点颜色不能相同，所以转移的时候只能由颜色不同的转移过来。且当前点的方案数应为其子树方案数的乘积。打个比方，对于点i来说,它有两个子树j,k。那么转移方程应为

dp[i][1]*=(dp[j][2]+dp[j][3])*(dp[k][2]+dp[k][3]);

dp[i][2]*=(dp[j][1]+dp[j][3])*(dp[k][1]+dp[k][3]);

dp[i][3]*=(dp[j][1]+dp[j][2])*(dp[k][1]+dp[k][2]);

至于为什么是*=，这就涉及到了dp初始值的设立。

对于一个最初没有涂色的点i，很显然刚遍历到的时候我们设置点i的初始值 dp[i][1]=dp[i][2]=dp[i][3]=1;

而如果点i已经被上色了，那么只有被上的颜色的数组才能为1(dp[i][col[i]]=1)，而其他2个都为0。

所以之前用*=来更新保证了如果当前点已经被上色了的话，上其他颜色的方案数为0。

然后随便选个点i为根跑一遍dfs输出dp[i][1]+dp[i][2]+dp[i][3]就好了

#include<cstdio>
#include<iostream>
#include<cstring>
#define p 1000000007
#define LL long long
using namespace std;
inline int read()
{
    int sum=0;
    char ch =getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum;
}
int n,m,tot=0;
int Head[100005],col[100005];//Head用于邻接表  col记录颜色
LL dp[100005][4];
bool visit[100005];//由于存图为无向图，所以要记录下已经走过的点防止死循环
struct tree
{
    int next,node;
}h[200010];
inline void add(int u,int v)//邻接表存图
{
    h[++tot].next=Head[u];
    h[tot].node=v;
    Head[u]=tot;
}
void dfs(int pos)//dfs遍历
{
    visit[pos]=1;
    if(col[pos])//如果已经上过色了，其他两种颜色的方案数为0。
        dp[pos][col[pos]]=1;
    else//三种颜色都可以被♂上
    {
        dp[pos][1]=1;
        dp[pos][2]=1;
        dp[pos][3]=1;
    }
    for(register int i=Head[pos];i;i=h[i].next)//找到当前点所有的子节点
    {
        int v=h[i].node;
        if(!visit[v])
        {
            dfs(v);//一直向下遍历直到叶子节点返回
            dp[pos][1]=dp[pos][1]*((dp[v][2]+dp[v][3])%p)%p;
            dp[pos][2]=dp[pos][2]*((dp[v][1]+dp[v][3])%p)%p;
            dp[pos][3]=dp[pos][3]*((dp[v][2]+dp[v][1])%p)%p;//转移  记得取模！
        }
    }
}
int main()
{
    int x,y;
    n=read();
    m=read();
    for(register int i=1;i<n;++i)
    {
        x=read();
        y=read();
        add(x,y);
        add(y,x);//加边
    }
    for(register int i=1;i<=m;++i)
    {
        x=read();
        y=read();
        col[x]=y;//记录颜色
    }
    dfs(1);//随便把一个点当根就好了
    cout<<(dp[1][1]+dp[1][2]+dp[1][3])%p<<endl;
    return 0;
}