trang chủ / đề bài / treeiso1

Đẳng cấu cây I

Đề bài

Mô tả

Cho hai cây có gốc, mỗi cây gồm n đỉnh đánh số từ 1 đến n, và gốc của cả hai cây đều là đỉnh 1.

Hai cây có gốc được gọi là đẳng cấu nếu có thể vẽ lại một cây (đổi tên các đỉnh và đổi thứ tự các con của mỗi đỉnh) để nó trông giống hệt cây còn lại, trong đó gốc phải tương ứng với gốc. Nói cách khác, tồn tại một song ánh f từ tập đỉnh cây thứ nhất sang tập đỉnh cây thứ hai sao cho f(1)=1 và u là cha của v trong cây thứ nhất khi và chỉ khi f(u) là cha của f(v) trong cây thứ hai.

Với mỗi bộ dữ liệu, hãy cho biết hai cây có đẳng cấu hay không.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên t, số bộ dữ liệu.
  • Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa số nguyên n.
  • n−1 dòng tiếp theo, mỗi dòng chứa hai số nguyên a,b mô tả một cạnh của cây thứ nhất.
  • n−1 dòng tiếp theo, mỗi dòng chứa hai số nguyên a,b mô tả một cạnh của cây thứ hai.

Dữ liệu ra

Với mỗi bộ dữ liệu, in YES nếu hai cây đẳng cấu, ngược lại in NO.

Ràng buộc

  • 1≤t≤1000
  • 2≤n≤105
  • Tổng các giá trị n không vượt quá 105
  • 1≤a,b≤n, a≠b; mỗi bộ n−1 cạnh tạo thành một cây

Ví dụ

Input Output Giải thích
2
3
1 2
2 3
1 2
1 3
3
1 2
2 3
1 3
3 2
NO
YES
Bộ 1: cây thứ nhất là đường đi 1−2−3 (gốc có một con), cây thứ hai có gốc với hai con. Bộ 2: cả hai cây đều là đường đi xuất phát từ gốc 1.
1
4
1 2
1 3
3 4
4 1
1 3
2 4
YES Ở cả hai cây, gốc có hai con: một con là lá, con còn lại có đúng một con là lá (f: 2→3, 3→4, 4→2).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0