P3914题解

Supor__Shoep · 2022-02-07 19:08:52 · 题解

也许你发现我和这里有某些题解长得差不多，但是真的是不一样的，因为我的代码量变长了。。

首先它就是一道简简单单的树形 DP，状态，转移，这些相似的题在洛谷上一抓一大把。说简单一点，这就是简简单单的动态规划加上简简单单的深搜，只要你学过哪怕一点点，就会把这道题轻轻松松一遍过。

但是我们要睁大自己的狗眼看看评测记录，我们会发现基本所有的人都惨遭 MLE，所以我们不能使用 long long 的数组。

问题是找到了，但是怎么解决呢？

很简单，只需要定义一个 long long 的变量，存放即将赋的值，最后在赋值的时候转化为 int 就可以了。

为了方便大家理解，举一个简单的小栗子：

int a[10];
long long Now;
Now=123;
Now+=123456789999;
Now-=123456700000;
a[1]=(int)Now;

现在大家应该知道自己为什么炸了。

然后说一下取模，经过了负数取模的教训之后，我们必须写成：

x=(x+MOD)%MOD;

这是因为负数取模在 C++ 里面和数学不太一样,不信就拿 -1 试试。

最后我给大家说一下本题动态规划。假设 f[i][j] 为 i 节点取颜色 j 时所有的值，sum[i] 为这个点所有的方案数，那么就可以简单推出：

f[当前节点][颜色]*=(sum[当前节点子节点]-df[当前节点子节点][对应颜色]+MOD)%MOD;
sum[当前节点]+=f[当前节点][颜色]%MOD;

为了完成 long long，我们可以用 Now 记录，转化为代码就是：

Now=(long long)((sum[G[i].next_to]-f[G[i].next_to][j])%MOD+MOD)%MOD;
Now=(long long)f[x][j]*Now%MOD;
f[x][j]=(int)Now;

再进行合理的收尾处理，就可以过了。

不妨亮一下代码：

void F(int x,int y)
{
    G[++k].Next=Top[x];
    G[k].next_to=y;
    Top[x]=k;   
}
void dfs(int x,int y)
{
    long long Now=0;
    for(int i=Top[x];i;i=G[i].Next)
    {
        if(G[i].next_to!=y)
        {
            dfs(G[i].next_to,x);
            for(int j=1;j<=m;j++)
            {
                Now=(long long)((sum[G[i].next_to]-f[G[i].next_to][j])%MOD+MOD)%MOD;
                Now=(long long)f[x][j]*Now%MOD;
                f[x][j]=(int)Now;
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        sum[x]=(sum[x]+f[x][i])%MOD;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        for(int j=1;j<=x;j++)
        {
            int y;
            cin>>y;
            f[i][y]=1;
        }
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        F(x,y);
        F(y,x);
    }
    dfs(1,0);
    cout<<sum[1];
    return 0;
}