NOI 2026 Day 2 T3 题解

· · 题解

设 dp_{x,i,j} 表示 x 子树内有 i 种颜色需要与祖先匹配，有 j 种独立的颜色不需要匹配，此时的方案数。

可以发现转移到的点就是 ([\max i,\sum i],[\max j,\sum j]) 这个矩形，只需要分别记录 (\max i,\max j),(\max i,\sum j),(\sum i,\max j),(\sum i,\sum j) 四个状态后二维前缀和即可。

最后还需要加入点 x 的贡献，也就是分成两种情况，x 在集合内的时候可以转移到 (i,j)(i\ge1) 和 (i+1,j)，x 不在集合内的时候可以转移到 (i-1,j+1)(i\ge1) 和 (i,j+1)。

为了避免算重，只需要把上面的四个状态中的 \sum i 改为 \sum i+1，最后再转移到 (i,j) 和 (i-1,j+1) 即可（需要保证 i\ge1）。

但是这样会算漏，因为即使 x 不在集合内，也可以与祖先有相同的颜色，因此也可以转移到 (i,j)。

但是这样又算重了，为什么呢？因为实际上如果两种转移 x 都不在集合内，一种情况下与祖先没有相同的颜色，一种情况下与祖先有相同的颜色，最终得到相同的 c 序列，这样就会算两遍。

考虑怎么处理这个问题，我们可以使用类似延迟钦定的技巧，因为一个子树内的任何一个点不论是否在集合内，都可以与祖先有相同的颜色。我们将不在集合内的点与祖先的匹配延迟考虑，或者说在固定 i+j 的情况下只保留 i 最小的状态，等到需要的时候再匹配，这样就不会算重了（也可以理解为对 i+j 相同的状态按照 i 做差分）。

现在转移就不一样了，我们转移到的点变成了一个矩形的左边界和上边界，这样只需要记三个顶点同样可以前缀和维护。

还有一个小问题，就是我们刚才说的延迟匹配，也就是如果要合并 (ix,jx) 和 (iy,jy)（假设 ix\le iy），它们转移到的颜色数最小的状态（也就是矩形的左下顶点）并不是直接合并得到的 (iy,\max\{jx,jy\})，而是 (iy,jx-(iy-ix)) 与 (iy,jy) 合并得到的 (iy,\max\{jx-(iy-ix),jy\})。

这样我们就以 O(n^4) 的时间复杂度完成了这道题，代码很短，只有 2.2k。

#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
const int mod = 998244353;
inline void inc(int &x, int y) { x = (x + y >= mod ? x + y - mod : x + y); }
inline void dec(int &x, int y) { x = (x < y ? x - y + mod : x - y); }
inline int add(int x, int y) { return (x + y >= mod ? x + y - mod : x + y); }
vector<int> v[210];
int siz[210], dp[210][210][210], f[210][210][210][3], g[210][210][3], s1[210][210], s2[210][210];
void dfs(int x)
{
    siz[x] = 1;
    f[x][1][0][0] = 1;
    f[x][1][0][1] = 1;
    f[x][1][0][2] = 1;
    for (auto y : v[x])
    {
        dfs(y);
        for (int ix = 0; ix <= siz[x]; ix++) for (int jx = 0; ix + jx <= siz[x]; jx++) for (int iy = 0; iy <= siz[y]; iy++) for (int jy = 0; iy + jy <= siz[y]; jy++)
        {
            if (ix <= iy) inc(g[iy][max(jx - (iy - ix), jy)][0], 1ll * f[x][ix][jx][0] * dp[y][iy][jy] % mod);
            else inc(g[ix][max(jx, jy - (ix - iy))][0], 1ll * f[x][ix][jx][0] * dp[y][iy][jy] % mod);
            inc(g[max(ix, iy)][jx + jy][1], 1ll * f[x][ix][jx][1] * dp[y][iy][jy] % mod);
            inc(g[ix + iy][jx + jy][2], 1ll * f[x][ix][jx][2] * dp[y][iy][jy] % mod);
        }
        siz[x] += siz[y];
        for (int i = 0; i <= siz[x]; i++) for (int j = 0; i + j <= siz[x]; j++)
        {
            f[x][i][j][0] = g[i][j][0], g[i][j][0] = 0;
            f[x][i][j][1] = g[i][j][1], g[i][j][1] = 0;
            f[x][i][j][2] = g[i][j][2], g[i][j][2] = 0;
        }
    }
    for (int i = 0; i <= siz[x]; i++) for (int j = 0; i + j <= siz[x]; j++) s1[i][j] = s2[i][j] = 0;
    for (int i = 0; i <= siz[x]; i++) for (int j = 0; i + j <= siz[x]; j++)
    {
        inc(s1[i][j], f[x][i][j][0]);
        dec(s1[i][j], f[x][i][j][1]);
        inc(s2[i][j], f[x][i][j][1]);
        dec(s2[i + 1][j], f[x][i][j][2]);
    }
    for (int i = 0; i <= siz[x]; i++) for (int j = 1; i + j <= siz[x]; j++) inc(s1[i][j], s1[i][j - 1]);
    for (int i = 1; i <= siz[x]; i++) for (int j = 0; i + j <= siz[x]; j++) inc(s2[i][j], s2[i - 1][j]);
    for (int i = 0; i <= siz[x]; i++) for (int j = 0; i + j <= siz[x]; j++)
    {
        int val = add(s1[i][j], s2[i][j]);
        inc(dp[x][i][j], val);
        if (i >= 1) inc(dp[x][i - 1][j + 1], val);
    }
}
int rainbow(int c, int n, vector<int> fa)
{
    for (int i = 1; i < n; i++) v[fa[i] + 1].push_back(i + 1);
    dfs(1);
    int ans = 0;
    for (int i = 0; i <= n; i++) inc(ans, dp[1][0][i]);
    return ans;
}

后记

赛时我在这道题上花费了两个小时，但是最终发现会算重放弃了这道题，获得了 0 分，这也导致我 Day 2 爆炸获得了 85+20+0=105 的分数。

这两天我一直在思考如果我不去做 T3 而是拼 T2 暴力或者冲 T2 正解会怎么样？似乎肯定会得到更高的分数，甚至可能接近或达到 Au 线。

回过头来再看这道题，我才意识到我的场上做法距离正解其实只有一步，可当时我的心态已经接近崩溃，没有办法进行有效的思考了。

即便如此，我并不后悔当时跳过 T2 做 T3 的这个决定。某种意义上，我是幸运的——我遵从了那一刻的直觉，赌过一次，并且已经无限接近胜利，只是最后差了那么一点运气。

也许，这正是 OI 最残忍也最迷人的地方：你永远不知道那一步之外是什么，但你也永远会为迈出那一步而心动。