Cho một cấu trúc cây vô hướng gồm đỉnh được đánh số từ đến . Đỉnh được xem là gốc của cấu trúc cây này. Khoảng cách giữa hai đỉnh bất kỳ là số cạnh trên đường đi đơn duy nhất nối giữa chúng.
Một dãy hoán vị gồm phần tử () của các đỉnh trên cây được gọi là có tính chất bảo toàn thứ tự lớp nếu nó thỏa mãn đồng thời hai điều kiện tiên quyết sau:
Đỉnh đầu tiên của dãy phải là gốc: .
Với mọi cặp đỉnh và bất kỳ (khác đỉnh ), gọi và lần lượt là cha trực tiếp của và trên cây. Nếu xuất hiện trước trong dãy , thì bắt buộc phải xuất hiện trước trong dãy . (Nếu , thứ tự giữa và là tùy ý).
Cho cấu trúc cây và một dãy hoán vị , hãy xác định xem dãy này có thỏa mãn tính chất bảo toàn thứ tự lớp hay không.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên () biểu thị số lượng nút trong cây.
dòng tiếp theo mô tả các cạnh của cây. Mỗi dòng chứa hai số nguyên và () — các đầu mút của cạnh tương ứng. Đảm bảo rằng đồ thị đã cho là một cây.
Dòng cuối cùng chứa số nguyên phân biệt () — dãy cần kiểm tra.
Kết quả:
In ra "Yes" nếu dãy thỏa mãn tính chất đã nêu, và "No" nếu ngược lại.
Ví dụ:
Dữ liệu:
4
1 2
1 3
2 4
1 2 3 4
Kết quả:
Yes
Dữ liệu:
4
1 2
2 3
3 4
1 4 3 2
Kết quả:
No
Dữ liệu:
6
1 2
1 3
2 4
2 5
3 6
1 3 2 6 4 5
Kết quả:
Yes
Giải thích:
Trong ví dụ thứ nhất: Cha của 2 là 1, cha của 3 là 1, cha của 4 là 2. Vị trí các cha trong dãy lần lượt là . Dãy vị trí cha là là dãy không giảm, nên thỏa mãn.
Trong ví dụ thứ hai: đúng. Nhưng xét và . Trong dãy , đứng sau nhưng lại đứng sau , vi phạm điều kiện thứ 2.
Giới hạn:
Subtask #1 (20% số điểm): .
Subtask #2 (30% số điểm): .
Subtask #3 (20% số điểm): Cây có dạng hình sao (đỉnh 1 nối với tất cả các đỉnh còn lại).
Subtask #4 (30% số điểm): Không có ràng buộc gì thêm ().
