1

problem： $n$ 个点，每个点有颜色，同色点不能连边，问生成树个数。 大概是 [这题](https://www.acmicpc.net/problem/21115) 的 $K=1$。 --- 多半是经典问题，但是没见过，也不会用 prufer 序做，就只能大力... 设颜色数为 $k$，每种颜色的数量分别为 $a_1,a_2,\cdots,a_k$。 拿 $k=3,a_1=a_2=a_3=3$ 举例， Kirchhoff 矩阵去掉第 $n$ 行第 $n$ 列为： $$\begin{bmatrix} n-a_1 & 0 & 0 & -1 & -1 & -1 & -1 & -1 \\ 0 & n-a_1 & 0 & -1 & -1 & -1 & -1 & -1 \\ 0 & 0 & n-a_1 & -1 & -1 & -1 & -1 & -1 \\ -1 & -1 & -1 & n-a_2 & 0 & 0 & -1 & -1 \\ -1 & -1 & -1 & 0 & n-a_2 & 0 & -1 & -1 \\ -1 & -1 & -1 & 0 & 0 & n-a_2 & -1 & -1 \\ -1 & -1 & -1 & -1 & -1 & -1 & n-a_3 & 0 \\ -1 & -1 & -1 & -1 & -1 & -1 & 0 & n-a_3 \\ \end{bmatrix}$$ 第 $2\sim n-1$ 列加到第一列： $$\begin{bmatrix} 1 & 0 & 0 & -1 & -1 & -1 & -1 & -1 \\ 1 & n-a_1 & 0 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & n-a_1 & -1 & -1 & -1 & -1 & -1 \\ 1 & -1 & -1 & n-a_2 & 0 & 0 & -1 & -1 \\ 1 & -1 & -1 & 0 & n-a_2 & 0 & -1 & -1 \\ 1 & -1 & -1 & 0 & 0 & n-a_2 & -1 & -1 \\ 0 & -1 & -1 & -1 & -1 & -1 & n-a_3 & 0 \\ 0 & -1 & -1 & -1 & -1 & -1 & 0 & n-a_3 \\ \end{bmatrix}$$ 第 $2\sim n-a_k$ 行分别减去第一行： $$\begin{bmatrix} 1 & 0 & 0 & -1 & -1 & -1 & -1 & -1 \\ 0 & n-a_1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & n-a_1 & 0 & 0 & 0 & 0 & 0 \\ 0 & -1 & -1 & n-a_2+1 & 1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 1 & n-a_2+1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 1 & 1 & n-a_2+1 & 0 & 0 \\ 0 & -1 & -1 & -1 & -1 & -1 & n-a_3 & 0 \\ 0 & -1 & -1 & -1 & -1 & -1 & 0 & n-a_3 \\ \end{bmatrix}$$ 设 $a$ 的前缀和数组为 $s$。 $\forall i\in[2,k-1]$，把第 $(s_{i-1}+2)\sim s_i$ 行都加到第 $(s_i+1)$ 行。 $$\begin{bmatrix} 1 & 0 & 0 & -1 & -1 & -1 & -1 & -1 \\ 0 & n-a_1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & n-a_1 & 0 & 0 & 0 & 0 & 0 \\ 0 & -1 & -1 & n & 1 & 1 & 0 & 0 \\ 0 & -1 & -1 & n & n-a_2+1 & 1 & 0 & 0 \\ 0 & -1 & -1 & n & 1 & n-a_2+1 & 0 & 0 \\ 0 & -1 & -1 & -a_2 & -1 & -1 & n-a_3 & 0 \\ 0 & -1 & -1 & -a_2 & -1 & -1 & 0 & n-a_3 \\ \end{bmatrix}$$ $\forall i\in[2,k-1]$，把第 $(s_{i-1}+2)\sim s_i$ 列分别减去第 $(s_i+1)$ 列。 $$\begin{bmatrix} 1 & 0 & 0 & -1 & -1 & -1 & -1 & -1 \\ 0 & n-a_1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & n-a_1 & 0 & 0 & 0 & 0 & 0 \\ 0 & -1 & -1 & n & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & n-a_2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & n-a_2 & 0 & 0 \\ 0 & -1 & -1 & -a_2 & -1 & -1 & n-a_3 & 0 \\ 0 & -1 & -1 & -a_2 & -1 & -1 & 0 & n-a_3 \\ \end{bmatrix}$$ 显然只能选择主对角线上的数乘起来。 答案就是： $$n^{k-2}\prod_{i=1}^k(n-a_i)^{a_i-1}$$ --- **扩展：**（那题也需要用到） 有 $P$ 个连通块，第 $i$ 个连通块颜色为 $c_i$，点数为 $t_i$。同色连通块不能相邻。问再把这些连通块连成一棵树的方案数，（$\sum t_i=n$，颜色数为 $k$。） 也就是混合了[这题](https://www.luogu.com.cn/problem/P5206)的某部分。 --- 还是手消。 设 $sc_i=\sum [c_j=i]t_j,a_i=\sum [c_j=i]$。 答案就是： $$n^{k-2}\prod_{i=1}^k(n-sc_i)^{a_i-1}\prod_{i=1}^P t_i$$