trang chủ / đề bài / treeiso2

Đẳng cấu cây II

Đề bài

Mô tả

Cho hai cây (không có gốc), mỗi cây gồm n đỉnh đánh số từ 1 đến n.

Hai cây được gọi là đẳng cấu nếu có thể vẽ lại một cây (đổi tên các đỉnh) để nó trông giống hệt cây còn lại. 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 u và v được nối bởi một cạnh trong cây thứ nhất khi và chỉ khi f(u) và f(v) được nối bởi một cạnh 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
YES
YES
Mọi cây 3 đỉnh đều là một đường đi. Bộ 1: f(1)=2, f(2)=1, f(3)=3.
1
4
1 2
2 3
3 4
1 2
1 3
1 4
NO Cây thứ nhất là đường đi, cây thứ hai có một đỉnh bậc 3.

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