M - Fractal Tree Isomorphism Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 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 から誘導される 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 からそれぞれ誘導される fractal tree (T_i)_\infty と (T_j)_\infty が同型か判定してください。

Fractal tree の同型性の定義 Fractal tree T の頂点集合を V(T) 、辺集合を E(T) とする。2 つの fractal tree S,T が同型であるとは、以下の 2 つの条件を満たす全単射 \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 回操作を施した木は以下の通りです。