设 $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 最残忍也最迷人的地方：你永远不知道那一步之外是什么，但你也永远会为迈出那一步而心动。