题解 P4084 【[USACO17DEC]Barn Painting】

LlLlCc · 2019-08-15 21:29:51 · 题解

经典的树形DP，适合入门练手

进入正题：

• f[i][j]表示i这个点上色为j是方案数（从下往上/从子节点向父节点更新）
• 即对于所有初始节点，f[i][1],f[i][2],f[i][3]都为1

• 当某个节点被指定上色后，那么该节点另外两种颜色的方案数为0。

  列如:当点x被指定上色 2 时：f[x][1]=0,f[x][3]=0 (因为无法上色1和3）

• 对于每个节点，因为不能于子节点上色相同,即：

   f[x][0]=f[x][0]*(f[son[i]][1]+f[son[i]][2]);
   f[x][1]=f[x][1]*(f[son[i]][0]+f[son[i]][2]);
   f[x][2]=f[x][2]*(f[son[i]][1]+f[son[i]][0]);

• 最后，记得取模和开long long

代码参考：

#include<bits/stdc++.h>
#define maxn 200005
#define ll long long
using namespace std;
const int TT=1e9+7;
int n,x,y,lnk[maxn],nxt[maxn],son[maxn],tot,m;
ll f[maxn][3];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
    while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void add(int x,int y){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
inline void Dfs(int x,int fa){
    for (int i=0;i<3;i++){
        if (f[x][i]){for (int j=0;j<i;j++) f[x][j]=0;break;}
        f[x][i]=1;
    }
    for (int i=lnk[x];i;i=nxt[i])
      if (son[i]!=fa){
        Dfs(son[i],x);
        f[x][0]=f[x][0]*((f[son[i]][1]+f[son[i]][2])%TT)%TT;
                f[x][1]=f[x][1]*((f[son[i]][0]+f[son[i]][2])%TT)%TT;
                f[x][2]=f[x][2]*((f[son[i]][1]+f[son[i]][0])%TT)%TT;
      }
}
int main(){
    n=read(),m=read();
    for (int i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
    for (int i=1;i<=m;i++) x=read(),y=read()-1,f[x][y]=1;
    Dfs(1,0);
    printf("%lld",(f[1][0]+f[1][1]+f[1][2])%TT);
    return 0;
}