题解：P17145 [NOI 2026] 彩虹树（暂无数据）

sbno333 · 2026-07-24 20:47:25 · 题解

闲话：赛时会掉这个题觉得这把可能能翻盘，但是没调出来，原因放在最后，反正本来能肘飞所有同学变成了被所有同学肘飞。

直接上手我们会考虑很多办法去判定，但是我们发现如果钦定某个规律点和谁相同，我们并不会算。

我们发现有一个意义不明的东西是特殊性质 A，为啥意义不明？首先它靠后，说明确实可能有用，而且似乎会简单很多。

考虑链。

我们发现如果钦定谁和谁相同仍然不可做。

但是我们仍然考虑钦定谁是规律点，目前规律确定，求序列种数。

考虑从后向前考虑，我们发现每次当前的值可以变成上一个值加一或者不变。

当加一的时候，显然不和任何人相等，不会有影响。

加一的时候，我们要求只统计一次，为了让之后不受限制，我们尽量和一个后面没匹配的一个规则点颜色匹配。如果不这样和这样考虑后面的贡献，发现匹配的方案更多并且是不匹配的方案的超集。也就是说我们希望最小化未匹配颜色个数。

如果当前是规则点，我们发现无论如何，最后的没匹配颜色会无视其它直接加一，因为显然别的未匹配颜色不可能和自己同色而合并，否则会在之前就会把那个颜色匹配掉。

设 dp_{i,j,k} 表示考虑了后 i 个点，c_i=j，所有钦定方式下有多少合法的 c 序列，满足可以让剩下未匹配颜色个数最少剩下 k 的方案数。

很明显状态可以扩展到正常树上，把 i 改成 i 子树即可。

但是和普通的树形 DP 不同，我们转移不能直接子树两两合并，原因是我们每次合并两个子树不会知道它们合并后的颜色种类数，但是合并过程会记录，导致算重，只有在最后合并因为有根记录颜色种类数，所以不会算重。

考虑 B 性质，枚举两个儿子的 DP 值的两维，分别记作 j_1,k_1,j_2,k_2，然后显然要把这两个位置的值乘起来，考虑转移给谁。

我们首先考虑所有人尽量不同，因为还有根，所以转移给 j_1+j_2+1,k_1+k_2，此时根难以帮助任何颜色摆脱困境并且未匹配颜色不产生合并。

如果颜色尽量相同，那就是 j 这维就是 \max(j_1,j_2)，k 这维下面会说。

我们对于 j 这维可以取到 \max(j_1,j_2)\sim j_1+j_2+1。

考虑随着 j 变小，我们的 k 的变化。

当转移给 j_1+j_2 时，k 这维可以让两个人合并，或者根和一个人匹配，但不管是啥，都只能减少 1，之后减少同理，而且根只能无差别减少一个，合并也不是可以无限减少，因为不能自己合并自己，所以只考虑合并，下限是 \max(k_1,k_2)，但是可以无差别减少，所以 k 这维下限就是 \max(\max(k_1,k_2)-1,0)。

于是枚举转移给的就是形如 \max(j_1,j_2)\le j\le j_1+j_2+1，k=\max((k_1+k_2)-(j_1+j_2+1-j),\max(\max(k_1,k_2),0))。

最后我们自己转移给自己就是 k 增加一。

考虑拓展，那就是每个子树选一个 j,k，然后下限是最大值，上限是和，直接用一个背包记录四个东西去算，复杂度 O(n^6)。

考虑对于每个对，我们贡献的本质其实是一段斜线和一段直线。

考虑拆掉这个，变成一个触底的斜线减去另一个触底的斜线加上一段接触到左边的直线减去接触到左边的直线。

对于第一个斜线，只关心两维和，可以直接卷积计算，复杂度 O(n^4)。

对于第二个斜线，只关心 j-k 的和和 k 的最大值，依然可以卷积计算，复杂度 O(n^4)。

对于第一段直线，我们关心的和上面一样，O(n^4) 卷积计算。

第二段则只考虑 j 的最大值和 k 的最大值，卷积计算，O(n^4)。

我们按照线类型分别跑前缀和然后贡献即可。

复杂度 O(n^4)。

#include<bits/stdc++.h>
#include "rainbow.h"
using namespace std;
#define int long long
const int mod=998244353;
int fa[209];
vector<int> s[209];
int dp[209][209][209];
int sz[209];
int f[209][209];
int g[209][209];
int gg[209][209];
void dfs(int t){
    sz[t]=1;
    for(auto v:s[t]){
        dfs(v);
        sz[t]+=sz[v];
    }
    if(s[t].size()==0){
        dp[t][1][0]=dp[t][1][1]=1;
        return;
    }
    int sm;
    for(int i=0;i<=sz[t]+2;i++){
        for(int j=0;j<=sz[t]+2;j++){
            f[i][j]=0;
        }
    }
    for(int i=0;i<=sz[t]+2;i++){
        for(int j=0;j<=sz[t]+2;j++){
            g[i][j]=0;
        }
    }
    g[1][0]=1;
    sm=1;
    for(auto v:s[t]){
        for(int i=0;i<=sz[t]+2;i++){
            for(int j=0;j<=sz[t]+2;j++){
                gg[i][j]=0;
            }
        }
        for(int i=0;i<=sm;i++){
            for(int j=0;j<=sm;j++){
                if(g[i][j]){
                    for(int x=0;x<=sz[v];x++){
                        for(int y=0;y<=sz[v];y++){
                            if(dp[v][x][y]){
                                gg[i+x][j+y]+=g[i][j]*dp[v][x][y];
                                gg[i+x][j+y]%=mod;
                            }
                        }
                    }
                }
            }
        }
        sm+=sz[v];
        for(int i=0;i<=sz[t];i++){
            for(int j=0;j<=sz[t];j++){
                g[i][j]=gg[i][j];
            }
        }
    }
    for(int i=0;i<=sz[t];i++){
        for(int j=0;j<=sz[t];j++){
            f[i][j]+=g[i][j];
        }
    }
    for(int i=sz[t];i>=0;i--){
        for(int j=sz[t];j>=0;j--){
            f[i][j]+=f[i+1][j+1];
            f[i][j]%=mod;
            dp[t][i][j]+=f[i][j];
            dp[t][i][j]%=mod;
        }
    }
    for(int i=0;i<=sz[t]+2;i++){
        for(int j=0;j<=sz[t]+2;j++){
            f[i][j]=0;
        }
    }
    for(int i=0;i<=sz[t]+2;i++){
        for(int j=0;j<=sz[t]+2;j++){
            g[i][j]=0;
        }
    }
    g[1][0]=1;
    sm=1;
    for(auto v:s[t]){
        for(int i=0;i<=sz[t]+2;i++){
            for(int j=0;j<=sz[t]+2;j++){
                gg[i][j]=0;
            }
        }
        for(int i=0;i<=sm;i++){
            for(int j=0;j<=sm;j++){
                if(g[i][j]){
                    for(int x=0;x<=sz[v];x++){
                        for(int y=0;y<=x;y++){
                            if(dp[v][x][y]){
                                gg[i+x-y][max(j,y)]+=g[i][j]*dp[v][x][y];
                                gg[i+x-y][max(j,y)]%=mod;
                            }
                        }
                    }
                }
            }
        }
        sm+=sz[v];
        for(int i=0;i<=sz[t];i++){
            for(int j=0;j<=sz[t];j++){
                g[i][j]=gg[i][j];
            }
        }
    }
    for(int i=0;i<=sz[t];i++){
        for(int j=0;j<=sz[t];j++){
            f[i+max(j-1,0ll)][max(j-1,0ll)]+=g[i][j];
        }
    }
    for(int i=sz[t];i>=0;i--){
        for(int j=sz[t];j>=0;j--){
            f[i][j]+=f[i+1][j+1];
            f[i][j]%=mod;
            dp[t][i][j]-=f[i][j];
            dp[t][i][j]+=mod;
            dp[t][i][j]%=mod;
        }
    }
    for(int i=0;i<=sz[t]+2;i++){
        for(int j=0;j<=sz[t]+2;j++){
            f[i][j]=0;
        }
    }
    for(int i=0;i<=sz[t]+2;i++){
        for(int j=0;j<=sz[t]+2;j++){
            g[i][j]=0;
        }
    }
    g[1][0]=1;
    sm=1;
    for(auto v:s[t]){
        for(int i=0;i<=sz[t]+2;i++){
            for(int j=0;j<=sz[t]+2;j++){
                gg[i][j]=0;
            }
        }
        for(int i=0;i<=sm;i++){
            for(int j=0;j<=sm;j++){
                if(g[i][j]){
                    for(int x=0;x<=sz[v];x++){
                        for(int y=0;y<=x;y++){
                            if(dp[v][x][y]){
                                gg[i+x-y][max(j,y)]+=g[i][j]*dp[v][x][y];
                                gg[i+x-y][max(j,y)]%=mod;
                            }
                        }
                    }
                }
            }
        }
        sm+=sz[v];
        for(int i=0;i<=sz[t];i++){
            for(int j=0;j<=sz[t];j++){
                g[i][j]=gg[i][j];
            }
        }
    }
    for(int i=0;i<=sz[t];i++){
        for(int j=0;j<=sz[t];j++){
            f[i+max(j-1,0ll)][max(j-1,0ll)]+=g[i][j];
        }
    }
    for(int i=sz[t];i>=0;i--){
        for(int j=sz[t];j>=0;j--){
            f[i][j]+=f[i+1][j];
            f[i][j]%=mod;
            dp[t][i][j]+=f[i][j];
            dp[t][i][j]+=mod;
            dp[t][i][j]%=mod;
        }
    }

    for(int i=0;i<=sz[t]+2;i++){
        for(int j=0;j<=sz[t]+2;j++){
            f[i][j]=0;
        }
    }
    for(int i=0;i<=sz[t]+2;i++){
        for(int j=0;j<=sz[t]+2;j++){
            g[i][j]=0;
        }
    }
    g[0][0]=1;
    sm=1;
    for(auto v:s[t]){
        for(int i=0;i<=sz[t]+2;i++){
            for(int j=0;j<=sz[t]+2;j++){
                gg[i][j]=0;
            }
        }
        for(int i=0;i<=sm;i++){
            for(int j=0;j<=sm;j++){
                if(g[i][j]){
                    for(int x=0;x<=sz[v];x++){
                        for(int y=0;y<=x;y++){
                            if(dp[v][x][y]){
                                gg[max(i,x)][max(j,y)]+=g[i][j]*dp[v][x][y];
                                gg[max(i,x)][max(j,y)]%=mod;
                            }
                        }
                    }
                }
            }
        }
        sm+=sz[v];
        for(int i=0;i<=sz[t];i++){
            for(int j=0;j<=sz[t];j++){
                g[i][j]=gg[i][j];
            }
        }
    }
    for(int i=0;i<=sz[t];i++){
        for(int j=0;j<=sz[t];j++){
            f[i-1][max(j-1,0ll)]+=g[i][j];
        }
    }
    for(int i=sz[t];i>=0;i--){
        for(int j=sz[t];j>=0;j--){
            f[i][j]+=f[i+1][j];
            f[i][j]%=mod;
            dp[t][i][j]-=f[i][j];
            dp[t][i][j]+=mod;
            dp[t][i][j]%=mod;
        }
    }

    for(int i=0;i<=sz[t];i++){
        for(int j=sz[t];j>=1;j--){
            dp[t][i][j]+=dp[t][i][j-1];
            dp[t][i][j]%=mod;
        }
    }
}
signed rainbow(signed c,signed n,std::vector<signed> f){
    for(int i=2;i<=n;i++){
        fa[i]=f[i-1]+1;
        s[f[i-1]+1].push_back(i);
    }
    dfs(1);
    int ans;
    ans=0;
    for(int i=1;i<=n;i++){
        ans+=dp[1][i][0];
        ans%=mod;
    }
    return ans;
}

我赛时第四个式子多写了个 -1，导致一分没有。

复评的时候调试改掉了这个，另外注意数组重复利用的时候要确保之前的不会影响现在的，计算和清空边界怎么写要想清楚。

最大的问题是重写的时候发现的，注意我们要计算 j-k 的和，我们转移的时候要求 k\le j,但是卷积给的式子两维完全没有这个要求，千万不要手残写上这个。