Module: băm


Problem

8 /8


Hầm trú ẩn

Theory Click to read/hide

Ngoài ra còn có một số cách để băm cây có rễ một cách hiệu quả. 
Một trong những phương pháp này được sắp xếp như sau:
Chúng tôi xử lý các đỉnh theo cách đệ quy, theo thứ tự duyệt theo chiều sâu. Chúng ta sẽ giả định rằng giá trị băm của một đỉnh bằng p. Đối với các đỉnh có con, đầu tiên chúng ta chạy thuật toán cho chúng, sau đó thông qua các con, chúng ta sẽ tính toán giá trị băm của cây con hiện tại. Để làm điều này, hãy coi giá trị băm của các cây con là một dãy số và tính giá trị băm từ dãy này. Đây sẽ là hàm băm của cây con hiện tại.
Nếu thứ tự của các cây con không quan trọng đối với chúng tôi, thì trước khi tính toán giá trị băm, chúng tôi sắp xếp chuỗi giá trị băm từ các cây con rồi tính giá trị băm từ chuỗi đã sắp xếp.

Bằng cách này, bạn có thể kiểm tra đẳng cấu của cây - chỉ cần đếm hàm băm mà không cần thứ tự trên các phần tử con (nghĩa là mỗi lần sắp xếp các hàm băm của phần tử con). Và nếu giá trị băm của các gốc khớp nhau thì các cây đó là đẳng cấu, ngược lại thì không.

Đối với những cây chưa có gốc, mọi thứ diễn ra theo cách tương tự, nhưng trọng tâm phải được lấy làm gốc. Hoặc xem xét một cặp băm nếu có hai trọng tâm.

Problem

Petya và Vasya nhiệt tình đóng vai điệp viên. Hôm nay họ đang lên kế hoạch cho nơi họ sẽ đến 
đã xác định được căn hầm bí mật và sở chỉ huy của chúng. 

Cho đến nay, Petya và Vasya đã quyết định rằng họ sẽ cần chính xác n boong-ke, được đánh số từ 1 đến n để đảm bảo bí mật. 
Một số trong số chúng sẽ được kết nối bằng các đường hầm hai chiều và để đảm bảo độ tin cậy cũng như bí mật, các đường hầm này sẽ có thể tiếp cận được từ bất kỳ boong-ke nào đến bất kỳ đường nào.
Petya và Vasya thậm chí đã quyết định boong-ke nào sẽ được nối với nhau bằng đường hầm, nhưng họ không thể chọn cái nào sẽ là trụ sở chính. 
Các chàng trai muốn chọn nó và chia các boongke còn lại cho nhau sao cho có số boongke bằng nhau.Chính xác là có hai đường hầm dẫn đến trụ sở chính: một đường hầm từ boongke của Vasya, đường hầm còn lại từ boongke của Petya. 
                                                                                   
Petya mệt mỏi trở về nhà, và vào buổi sáng, Vasya cho anh xem một sơ đồ, trên đó các boongke được đánh dấu bằng các dấu chấm và các đường hầm có các đoạn. 
Ngoài ra, Vasya đã chọn trụ sở sao cho sơ đồ mà anh vẽ đối xứng với một đường thẳng đi qua điểm tương ứng với trụ sở.
 
Mặc dù Petya gần như ngay lập tức cho Vasya thấy rằng anh ta đã phạm sai lầm và không vẽ một nửa số boongke, nhưng anh ta tự hỏi liệu có thể chọn một trụ sở và vẽ một kế hoạch đối xứng như vậy không.

Đầu vào:
Dòng đầu tiên của tệp đầu vào chứa một số nguyên n (1 <= n <= 105) - số lượng thùng. 
N - 1 dòng tiếp theo chứa 2 số nguyên ui và vi (1 <= ui, vi <= n, ui ≠ vi) - số lượng boongke được kết nối bởi đường hầm thứ i. 
Đảm bảo rằng chỉ có một lối đi duy nhất giữa hai boong-ke bất kỳ.

Đầu ra:
Trong tệp đầu ra, in "CÓ" nếu có thể chọn trụ sở chính và vẽ một kế hoạch như vậy, hoặc "KHÔNG" nếu điều đó là không thể.

Ví dụ:
 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

Đầu vào Đầu ra
2
1 2 		KHÔNG
3
1 2
2 3 		CÓ