自动搬运

查看原文

来自洛谷，原作者为

	Ryo_Yamada **

搬运于2025-08-24 22:37:37，当前版本为作者最后更新于2022-04-10 22:11:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

高复杂度做法。

看到 $k=5$，可以思考一些复杂度带 $2^k$ 或 $k!$ 的做法。

我们发现从 $u$ 子树中选两个点 $x,y$ 使 $lca=u$，一定是 $x, \, y$ 属于 $u$ 两个不同的儿子的子树。于是如果我们知道了 $u$ 每个儿子的子树用了的颜色集合，就可以算出 $u$ 需要选的颜色（或无解）。

考虑先预处理出 $\text{trs}_{i,j}$ 表示：若对于一个节点 $u$ 的两个儿子 $x,\,y$，它们用了的颜色集合为 $i,\,j$，则 $u$ 需要用什么颜色（$-1$ 表示无解）。这个过程可以直接 $k^2 \times 2^{2k}$ 做。

接下来考虑如何进行树形dp。设 $dp_{u,i,j}$ 表示对于节点 $u$，当它用颜色 $i$ 且它的子树（不包括 $u$ 本身）所用颜色集合为 $j$ 时的方案数。

首先，对于每个叶子节点 $x$ 都有 $dp_{x,i,0}=1$。
对于非叶子节点 $u$，枚举它的每个叶子节点 $v$。枚举 $u$ 当前用的颜色集合 $j$ 和 $v$ 的状态 $dp_{v,i',j'}$。若 $\text{trs}_{j,j'} \not= -1$，令 $js=j' | \, 2^{i'-1}$ 则可以转移到 $dp_{u,\text{trs}_{i, js}, i|js}$。最终时间复杂度 $O(nk \times 2^{2k})$，空间复杂度 $O(nk \times 2^k)$。能过也是奇迹（。

$\text{Code}$：

def(N, int, 1e5 + 5)
def(p, int, 1e9 + 7)

int n, k, sta;
int to[6][6];
int trs[1 << 5][1 << 5];
vector<int> e[N];
int dp[N][6][1 << 5], f[N][6][1 << 5];

int get(int x, int y) {
	int res = 0;
	rep(i, 1, k) {
		if(!(x >> (i - 1) & 1)) continue;
		rep(j, 1, k) {
			if(!(y >> (j - 1) & 1)) continue;
			if(!res) res = to[i][j];
			else if(res != to[i][j]) res = -1;
		}
	}
	swap(x, y);
	rep(i, 1, k) {
		if(!(x >> (i - 1) & 1)) continue;
		rep(j, 1, k) {
			if(!(y >> (j - 1) & 1)) continue;
			if(!res) res = to[i][j];
			else if(res != to[i][j]) res = -1;
		}
	}
	return res;
}

void dfs(int u) {
	if(!e[u].size()) {
		rep(i, 1, k) dp[u][i][0] = 1;
		return ;
	}
	
	rep(l, 0, e[u].size() - 1) {
		int v = e[u][l];
		dfs(v);
		
		if(!l) {
			rep(nw, 1, k) rep(i, 0, sta) rep(j, 1, k) dp[u][nw][i | (1 << j - 1)] = (dp[u][nw][i | (1 << j - 1)] + dp[v][j][i]) % p;
			continue;
		}
		
		rep(i, 1, sta) rep(j, 1, k) f[u][j][i] = dp[u][j][i], dp[u][j][i] = 0;
		
		rep(i, 1, sta) {
			if(!dp[v][i]) continue;
			rep(j, 0, sta) {
				rep(nw, 1, k) {
					int js = (j | (1 << nw - 1));
					if(trs[i][js] == -1) continue;
					dp[u][trs[i][js]][i | js] = (dp[u][trs[i][js]][i | js] + 1ll * f[u][trs[i][js]][i] * dp[v][nw][j] % p) % p;
				}
			}
		}
	}
}

int main() {
	int t; cin >> t;
	W(t) {
		qread(n, k);
		sta = (1 << k) - 1;
		rep(i, 1, n) e[i].clear();
		rep(i, 1, k) rep(j, 1, k) qread(to[i][j]);
		rep(i, 2, n) {
			int f; qread(f);
			e[f].pb(i);
		}
		rep(i, 1, sta) rep(j, 1, sta) trs[i][j] = get(i, j);
		rep(i, 1, n) {
			memset(dp[i], 0, sizeof dp[i]);
			memset(f[i], 0, sizeof f[i]);
		}
		dfs(1);
		ll ans = 0;
		// rep(i, 1, n) rep(l, 1, n) rep(j, 0, sta) printf("dp[%d][%d][%d] : %lld\n", i, l, j, dp[i][l][j]);
		rep(l, 1, k) rep(i, 1, sta) ans = (ans + dp[1][l][i]) % p;
		cout << ans << '\n';
	}	
	return 0;
}