Submit solution
Points:
200.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Cho một đơn đồ thị liên thông gồm N đỉnh và N−1 cạnh. Mỗi cạnh có độ dài bằng 1. Ta nói đây là một cây không trọng số. Đường kính của cây là khoảng cách giữa hai đỉnh xa nhau nhất. Tâm của cây là đỉnh mà có khoảng cách từ nó tới nút xa nó nhất là nhỏ nhất. Một cây có thể có nhiều tâm. Hãy tìm đường kính của cây và các tâm của cây.
Dữ liệu vào:
- Dòng đầu tiên chứa số nguyên dương N
- N−1 dòng tiếp theo, mỗi dòng gồm hai số nguyên dương x và y chỉ một cạnh nối giữa hai đỉnh x và y trên cây.
Giới hạn:
- 1 ≤ N ≤ ~10^5~
Kết quả:
- Dòng đầu tiên, in ra đường kính của cây.
- Dòng thứ hai, in ra số lượng tâm của cây.
- Dòng thứ ba, in ra các đỉnh là tâm của cây theo thứ tự tăng dần. Các số cách nhau bởi 1 dấu cách.
Ví dụ:
Input 1:
5
1 2
2 3
3 4
2 5
Output 1:
4
2
2 3
Comments
Ta có vài khái niệm cần chú ý:
Tâm của cây là nút nằm giữa trên đường kính. Một cây sẽ có tối đa 2 tâm. (Nếu đường kính độ dài chẳn (độ dài tính theo cạnh) thì tâm sẽ là nút ở giữa, ngược lại nếu là lẻ thì là 2 nút ở giũa. Nếu trường hợp có hai hay nhiều hơn các đường kính, thì các đường kính sẽ có cùng độ dài và cắt nhau ở tâm. Điều này không cần phải bận tâm khi cài đặt, ta chỉ cần tìm 1 đường kính duy nhất và tìm tâm của nó, tâm đó sẽ là tâm của tất cả các đường kính và cũng là tâm của cây).
Ví dụ :![enter image description here](/static/blank.gif)
Đoạn từ nút 4 tới nút 5 sẽ là đường kính của cây, có độ dài là 3. (Tuy nhiên, trong bài này thì mình cần cho output là số đỉnh trên đường kính chứ không phải độ dài, dù là câu hỏi nào thì việc trả lời cũng tương đương nhau.) Tâm của cây sẽ là nút 2 và 3.
Đường đi giữa hai nút bất kì trên cây là duy nhất.
Thuật toán:
Cài đặt:
GoodLuck