首页 > 其他 > 详细

P3914 染色计数

时间:2019-08-24 20:55:14      阅读:120      评论:0      收藏:0      [点我收藏+]

技术分享图片

——————————————————————————————————————————————————————

普通树形计数题,就是犯了个傻逼错误

——————————————————————————————————————————————————————

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n,m,ne,head[5200],a,b,f[5050][5050],sum[5200],tot[5200];
struct node {int to,nxt;}eg[5200<<1];
void adde(int u,int v){eg[++ne].to=v;eg[ne].nxt=head[u];head[u]=ne;}
void dfs(int u,int fa)
{
    for(int i=head[u];i;i=eg[i].nxt)if(eg[i].to!=fa)dfs(eg[i].to,u);
    for(int j=1;j<=m;j++)
    if(f[u][j])
    {
        for(int i=head[u];i;i=eg[i].nxt)
        {
            int v=eg[i].to;
            if(v==fa)continue;
            f[u][j]=1LL*f[u][j]*(tot[v]-f[v][j])%mod;
        }
        while(f[u][j]<0)f[u][j]+=mod;
        tot[u]=(1LL*f[u][j]+1LL*tot[u])%mod;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {scanf("%d",&b);sum[i]=b;
    while(b--){scanf("%d",&a);f[i][a]++;}}
    for(int i=1;i<n;i++){scanf("%d%d",&a,&b);adde(a,b);adde(b,a);}
    adde(0,1);dfs(0,0);
    cout<<tot[1];
}

 

P3914 染色计数

原文:https://www.cnblogs.com/SFWR-YOU/p/11405958.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!