题解

思路

把矩阵看成无向图的邻接矩阵。

做法

若某个连通块来自一棵有根子树，那么它的根一定与块内所有点都有祖先关系，也就是图中的“全邻接点”；删去根以后，剩余的各连通块恰好对应不同的儿子子树。反过来，如果一个非空连通块找不到全邻接点，它就不可能由任何有根树产生。整棵树的根固定为结点 $1$，因此首先要检查它是否与所有点相邻，然后删去它并分别处理剩余连通块。

一个块中可能同时出现 $k$ 个全邻接点，它们必然在树上形成一条公共祖先链，顺序可以任意排列，贡献 $k!$ 种。一次删去这 $k$ 个点，将剩余图重新分成连通块递归，并把阶乘与各子块答案相乘即可。

复杂度

直接扫描矩阵寻找全邻接点和连通块，时间复杂度为 $O(N^3)$，空间复杂度为 $O(N^2)$。