← 返回题目列表

AtCoder · tupc2022_m

M. 分形树同构

中文机器翻译题面 查看原题

配点 : 400 点

問題文

带根树 S 对于带根树 f(S) ,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 从中导出的 分形树 称为。


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) 为例。两个分形树 S,T 同构的意思是存在一个满足以下两个条件的全单射 \varphi:V(S)\to V(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

制約

  • 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)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

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

4
2 1
3 1 2
3 1 1
5 1 1 2 2

出力例 1

1100
1100
0011
0011

给定的树如下。

对这些树 1 次操作后得到的树如下。