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

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

Với hai cây có gốc, tìm xem chúng có đẳng cấu hay không, tức là có thể vẽ sao cho chúng giống nhau.

Input

  • Dòng đầu tiên chứa số nguyên \(t\): số test cases. Mỗi test cases được mô tả như sau:
  • Dòng đầu tiên có số nguyên \(n\): số nút trong cả hai cây. Các nút được đánh số \(1,2,\dots,n\) và nút \(1\) là nút gốc.
  • \(n - 1\) dòng tiếp theo mô tả các cạnh của cây thứ nhất.
  • \(n - 1\) dòng tiếp theo mô tả các cạnh của cây thứ hai.

Output

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

Constraints

  • \(1\leq t \leq 1000\)
  • \(1 \leq n \leq 10^5\)
  • Tổng của \(n\) trong các test cases \(\leq 10^5\)

Example

Sample input

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

Sample output

NO  
YES

Bình luận


  • -1
    Thanh72    3:13 p.m. 19 Tháng 8, 2023

    Cho hai cây có gốc, hãy kiểm tra xem chúng có đẳng cấu hay không, tức là có thể vẽ sao cho chúng giống nhau.

    Input

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

    Output

    • Với mỗi test cases, in YES nếu 2 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 
    NO
YES