Let \(S_i\) be the set of \(j\) such that \(A_{i,j}=1\), then \(S_i\) represents the set of vertices which is either in \(i\)’s subtree of are \(i\)’s ancestor.

For any \(j\) such that \(A_{i,j}=1\), if \(S_i\) and \(S_j\) doesn’t include one another, then it’s easy to observe that there is no solution. Otherwise, if \(S_i\ne S_j\), than it would be unique whether \(i\) is \(j\)’s ancestor or vice versa.

However, we still have to consider the case \(S_i=S_j\). For now, since either way is OK, we will assume \(i\) is \(j\)’s ancestor if \(i<j\) in this case.

Suppose now that all conditions are satisfied, and we have decided for every pair \(i,j\) which one is the other’s ancestor, then there would be a unique tree satisfying the conditions.

This can be done by starting from \(1\), and classifying all nodes into subtrees. For any pair of \(i,j\) such that \(S_i\) and \(S_j\) doesn’t include on another, from the analysis above, we can see that \(A_{i,j}=A_{j,i}=0\) (otherwise this would be a pair not satisfying the condition, and the answer should be \(0\)), and hence \(i,j\) must be in separate subtrees.

So we delete \(1\), put the other nodes into groups, where two nodes \(i,j\) are in the same group if and only if \(S_i\cap S_j\ne\emptyset\) (remember that we have deleted node \(1\) from all \(S_i\) as well). This leads to smaller subproblems which can be solved by induction.

Therefore, all we have to do is to count the number of ways to set the ancestor relationships. The only part that can change is when \(S_i=S_j\). It’s easy to see that the two ways are symmetric, so we can freely choose the order of all nodes having the same \(S_i\). The number of ways for a single \(S\) is thus \(c!\), where \(c\) is the number of \(j\) such that \(S_j=S\). The case where \(S=S_1\) is special, since \(1\) must be the root. In this case, the number of ways is \((c-1)!\).

So the final solution is to first check for every pair \(A_{i,j}=1\), whether \(S_i\subseteq S_j\) or vice versa. Then classify all nodes into classes by \(S_i\), and count the size of every class, getting the answer. By using bitset, the complexity is \(O(\frac{n^3}{\omega})\).

code