CSES Tree Isomorphism II | Cây Đẳng Cấu II

Xem PDF
Tác giả:
ngpin_04
Dạng bài
Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho hai cây (không có gốc), nhiệm vụ của bạn là kiểm tra xem chúng có đẳng cấu hay không, tức là, có thể vẽ chúng sao cho chúng trông giống nhau.

Input

Dòng đầu vào đầu tiên có một số nguyên \(t\): số lượng test. Sau đó, có \(t\) test được mô tả như sau:

Dòng đầu tiên có một số nguyên \(n\): số nút trong cả hai cây. Các nút được đánh số \(1, 2, \ldots, n\).

Sau đó, có \(n − 1\) dòng mô tả các cạnh của cây thứ nhất, và cuối cùng là \(n − 1\) dòng mô tả các cạnh của cây thứ hai.

Output

Đối với từng test, in YES nếu các cây đẳng cấu và NO nếu ngược lại.

Constraints

  • \(1 \leq t \leq 1000\)
  • \(2 \leq n \leq 10 ^ 5\)
  • Tổng của tất cả các giá trị của \(n\) nhiều nhất là \(10 ^ 5\)

Example

Input:

2  
3  
1 2  
2 3  
1 2  
1 3  
3  
1 2  
2 3  
1 3  
3 2

Output:

YES  
YES

Bình luận


  • 0
    vanphukhang_0604    12:21 a.m. 26 Tháng 8, 2023 ← chỉnh sửa 2

    CSES Tree Isomorphism II | Cây đẳng cấu II

    Cho hai cây (không có gốc), hãy kiểm tra tính đẳng cấu của chúng, tức là xác định xem liệu có thể vẽ chúng sao cho chúng trông giống nhau hay không.

    Input

    • Dòng đầu tiên chứa một số nguyên \(t \ (1 \leq t \leq 1000)\): số lượng test.
    • Sau đó có \(t\) test được mô tả như sau:
      • Dòng đầu tiên có một số nguyên \(n \ (2 \leq n \leq 10^5)\): số nút trong mỗi cây. Các nút được đánh số \(1, 2, \ldots, n\). Tổng các giá trị \(n\) không quá \(10^5\).
      • \(n - 1\) dòng tiếp theo mô tả các cạnh của cây thứ nhất, mỗi dòng gồm hai số nguyên \(a\) và \(b\): có một cạnh nối giữa hai nút \(a\) và \(b\).
      • \(n - 1\) dòng tiếp theo mô tả các cạnh của cây thứ hai, cách mô tả như trên.

    Output

    • Với mỗi test, in YES nếu hai cây đã cho là hai cây đẳng cấu, ngược lại in NO.

    Example

    Test 1

    Input 
    2
3
1 2
2 3
1 2
1 3
3
1 2
2 3
1 3
3 2
    Output 
    YES
YES