AT_tupc2022_m Fractal Tree Isomorphism

对于一棵有根树 $S$，定义 $f(S)$ 为如下操作后的有根树： - 用树 $S$ 自身替换 $S$ 的所有叶子节点。 对于有根树 $S$，定义一组无穷序列的树 $(S_1, S_2, \dots)$，具体为： - $S_1 := S$ - $S_i := f(S_{i-1}) \quad (i > 1)$ 定义无穷树 $S_{\infty}:= \displaystyle\lim_{n\to\infty} S_n$，称其为由 $S$ 导出的**分形树**（fractal tree）。 --- 给定 $K$ 棵有根树 $T_1, T_2, \dots, T_K$。每棵树 $T_i\,(i=1,2,\dots,K)$ 满足以下条件： - 顶点数为 $N_i \geq 2$ - 顶点依次编号为 $1,2,\dots,N_i$ - 根为编号 $1$ 的顶点 - 对于 $j=2,3,\dots,N_i$，顶点 $j$ 的父节点为 $p_{i,j}$ 请对于每一对 $(i,j) \, (i,j=1,2,\dots,K)$，判断由 $T_i,T_j$ 各自导出的分形树 $(T_i)_\infty$ 和 $(T_j)_\infty$ 是否同构。 分形树的同构定义如下： 记分形树 $T$ 的顶点集合为 $V(T)$，边集合为 $E(T)$。若存在一个双射 $\varphi:V(S)\to V(T)$，使得以下两个条件成立，则称两棵分形树 $S,T$ 同构： - $\{u,v\}\in E(S) \iff \{\varphi(u),\varphi(v)\}\in E(T)$ - $S,T$ 的根节点分别为 $r_S, r_T$ 时，$\varphi(r_S)=r_T$

输入格式如下，经标准输入给出： > $K \ N_1 \ p_{1,2} \ p_{1,3} \ \dots \ p_{1,N_1} \ N_2 \ p_{2,2} \ p_{2,3} \ \dots \ p_{2,N_2} \ \vdots\ N_K \ p_{K,2} \ p_{K,3} \ \dots \ p_{K,N_K}$

输出 $K$ 行。第 $i$ 行输出长度为 $K$ 的仅由 `0` 或 `1` 组成的字符串。 第 $i$ 行的第 $j$ 个字符，如果 $(T_i)_\infty$ 和 $(T_j)_\infty$ 同构则为 `1`，否则为 `0`。

### 样例解释 1 给定的树如下所示。  对这些树进行一次操作后的结果如下所示。  ### 数据范围 - $2 \leq K \leq 1000$ - $2 \leq N_i \leq 5\times 10^4 \quad (1\leq i\leq K)$ - $\displaystyle\sum_{i=1}^K N_i \leq 10^5$ - $1 \leq p_{i,j} < j \quad (1 \leq i \leq K,\,2\leq j \leq N_i)$ - 所有输入均为整数。 由 ChatGPT 5 翻译