P3914染色计数

题目描述

有一颗\(N\)个节点的树，节点用\(1,2,\cdots,N\)编号。你要给它染色，使得相邻节点的颜色不同。有\(M\)种颜色，用\(1,2,\cdots,M\)编号。每个节点可以染\(M\)种颜色中的若干种，求不同染色方案的数量除以(\(10^9 + 7\))的余数。

输入输出格式

输入格式：

第1 行，2 个整数\(N,M\)。

接下来\(N\)行，第\(i\)行表示节点\(i\)可以染的颜色。第1个整数\(k_i\)，表示可以染的颜色数量。接下来\(k_i\)个整数，表示可以染的颜色编号。

最后\(N - 1\)行，每行2个整数\(A_i,B_i\)，表示边\((A_i,B_i)\)。

树形dp

dp方程

\(f[u][i]*=∑f[to][x]\) \(x!=i\)

#include<bits/stdc++.h>

using namespace std;

const int mod=1e9+7;

const int maxn=5000+10;

int f[maxn][maxn];//点i染成j的方案数

int sum[maxn],head[maxn];

int size=0;

int n,m;

struct edge

{

    int to,next,val;

}e[maxn<<1];

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch>'9'||ch<'0'){if(x=='-')f=-1;ch=getchar();}

    while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

void addedge(int u,int v)

{

    e[++size].to=v;

    e[size].next=head[u];

    head[u]=size;

}

void dfs(int u,int fa)

{

    for(int i=head[u];i;i=e[i].next)

    {

        int to=e[i].to;

        if(to==fa)continue;

        dfs(to,u);

        for(int i=1;i<=m;i++)

        {

            f[u][i]=((long long)f[u][i]*(sum[to]-f[to][i]+mod)%mod)%mod;

        }

    }

    for(int i=1;i<=m;i++)

    sum[u]+=f[u][i],sum[u]%=mod;

}

int main()

{

    n=read(),m=read();

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

    {

        int k=read();

        for(int j=1;j<=k;j++)

        f[i][read()]=1;

    }

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

    {

    int u=read(),v=read();

    addedge(u,v),addedge(v,u);

    }

    dfs(1,0);

    printf("%d",sum[1]);

    return 0;

}