题解：P17145 [NOI 2026] 彩虹树

WorldMachine · 2026-11-09 20:13:01 · 题解

很深刻的题。

题目所求等价于：有多少对 (c,S)，使得存在一种合法的染色方案。

碰到这种长相奇特的计数题，可以先想一下怎么判定。

首先显然要有 \displaystyle{\max_{v\in\text{son}(u)}\{c_v\}\le c_u\le\sum_{v\in\text{son}(u)}c_v}+1，再考虑 S 的限制。

设 dp_u 表示 u 子树内，需要往 u 的祖先（不含 u）寻求匹配的颜色数的最小值，有解当且仅当 dp_1=0。

考虑 dp 的转移。

先合并子树，对于子树 v，它必须要向外送出 dp_v 种颜色，不同子树间的外部颜色可以合并，这部分下界为 \displaystyle{\max_{v\in\text{son}(u)}\{dp_v\}}。

同时对于整棵子树，所有儿子内部颜色有 c_v-dp_v 种，即使全部分配完，也仍然需要 \displaystyle{c_u-\sum_{v\in\text{son}(u)}(c_v-dp_v)} 种额外颜色伸出去。

内部外部两类颜色是独立的，因此下界可以分别取到。因此 u 子树（不含 u）的 dp 值为：

再考虑加入 u，有两种情况：

于是现在可以做到 \mathcal O(N) 判定。

下一步肯定是要 DP of DP 了。

设 f_{u,dp,c} 表示 u 的对应状态的方案数。

然而由于 c_u 的范围限制，合并背包时需要记录：

然后这样状态就是四维的，直接做是 \mathcal O(N^6) 的。

想到容斥，分不限制 c_u、限制 c_u<\max_c、限制 c_u>\text{sum}_c+1 三种情况 DP。

第一种是好做的：只需维护计算子树下界所需的两个量 \max_{dp} 和 \text{sum}_\Delta 即可。

对于第二种，限定 c_u<\max_c，观察 \max(\max_{dp},c_u-\text{sum}_\Delta)，由于 \text{sum}_\Delta\ge\max_\Delta，且 \max\{a_i-b_i\}\ge\max\{a_i\}-\max\{b_i\}，有：

也就是说这时只需要考虑 \max_{dp}！那么转移时只用记录 \max_{dp} 和 \max_c 即可。

对于第三种，限定 c_u>\text{sum}_c+1，类似地有：

也就是说这时只需要考虑 c_u-\text{sum}_\Delta！那么转移时只用记录 \text{sum}_\Delta 和 \max_c 即可。

至此状态变成二维的，这部分转移就变成了 \mathcal O(N^4)。

加入 u 是容易的，按照判定部分的讨论，直接加上去即可。

代码还是很好写的。

#include <bits/stdc++.h>
// #include "rainbow.h"
using namespace std;
#define il inline
#define For(i, l, r) for (int i = (l), _r_ = (r); i <= _r_; i++)
typedef long long ll;
const int N = 205, P = 998244353;
il void _a(int &x, int y) { (x += y) >= P && (x -= P); }
il void _d(int &x, int y) { (x -= y) <  0 && (x += P); }
int n, sz[N], f[N][N][N], g[N][N], tp[N][N];
basic_string<int> G[N];
/*
首先有 max c[v] <= c[u] <= (sum c[v]) + 1
设 u 子树内 需要到 u 上面找匹配的 颜色数 最小为 dp[u]
有解  <=>  dp[1] = 0
可以得到 dp 的转移，塞到 dp of dp 里面
要记录 sum dp[v]，sum c[v]，max dp[v]，max c[v]
问题卡在第一行说的限制，但可以定向容斥掉

o  =  1：c[x] 无限制
    状态：g[max dp[v]][sum (c[v] - dp[v])]
o  =  0：c[x] < max c[v]
    状态：g[max dp[v]][max c[v]]
o  = -1：c[x] > (sum c[v]) + 1
    状态：g[sum c[v]][sum (c[v] - dp[v])]

这样限制变成二维的，复杂度 O(N^4)
*/
void DP(int u, int o) {
    For(i, 0, n) For(j, 0, n) g[i][j] = 0; sz[u] = 0, g[0][0] = 1;
    for (int v : G[u]) {
        For(i, 0, sz[u]) For(j, 0, sz[u]) tp[i][j] = g[i][j], g[i][j] = 0;
        For(i, 0, sz[u]) For(j, 0, sz[u]) if (tp[i][j]) For(x, 0, sz[v]) For(y, x, sz[v])
            _a(g[~o ? max(i, x) : i + y][!o ? max(j, y) : j + y - x], (ll)tp[i][j] * f[v][x][y] % P);
        sz[u] += sz[v];
    }
    For(i, 0, sz[u]) For(j, 0, sz[u]) if (g[i][j]) {
        if (o > 0) For(k, 0, sz[u] + 1) _a(f[u][max(i, k - j)][k], g[i][j]);
        else if (!o) For(k, 0, j - 1) _d(f[u][i][k], g[i][j]);
        else For(k, max(i + 1 + 1, j), sz[u] + 1) _d(f[u][k - j][k], g[i][j]);
    }
}
void dfs(int u) {
    if (G[u].empty()) return void(f[u][0][1] = f[u][1][1] = sz[u] = 1);
    for (int v : G[u]) dfs(v); for (int o : {1, 0, -1}) DP(u, o); sz[u]++;
    For(i, 0, sz[u]) For(j, 0, sz[u]) tp[i][j] = f[u][i][j], f[u][i][j] = 0;
    /*   i == 0   */ For(j, 0, sz[u]) _a(f[u][0][j], tp[0][j]), _a(f[u][1][j], tp[0][j]);
    For(i, 1, sz[u]) For(j, 0, sz[u]) _a(f[u][i - 1][j], tp[i][j]), _a(f[u][i][j], tp[i][j]);
}
int rainbow(int c, int n, vector<int> f) {
    ::n = n; For(i, 1, n - 1) G[f[i] + 1] += i + 1;
    return dfs(1), accumulate(::f[1][0], ::f[1][0] + 1 + n, 0ll) % P;
}
#ifdef WorldMachine
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int c, n; cin >> c >> n; vector<int> f(n);
    for (int i = 1; i < n; i++) cin >> f[i];
    cout << rainbow(c, n, f);
}
#endif