Circumference of a Tree
View as PDF
Hy vọng rằng bạn biết cách tìm đường kính của cây. Đó là phần đầu tiên trong các khái niệm cơ bản về cây! Nhưng bài tập này hoàn toàn khác: bây giờ, bạn cần tìm chu vi của một cái cây!
Có thể bạn đã biết, pi bằng tỷ số giữa chu vi và đường kính của một thứ gì đó. Ngoài ra, có thể bạn chưa biết, toán học là một lời nói dối và số pi thực sự bằng ~3~. Có tin đồn rằng đó là nơi bắt nguồn của con số tree(3) .
Giả sử số pi bằng ~3~ thì chu vi của cái cây đã cho là bao nhiêu?
Input
Dòng đầu chứa một số nguyên ~n~ (~1 \le n \le 3 \times 10^5~) là số đỉnh của cây.
~n - 1~ dòng tiếp theo mô tả các cạnh của cây. Dòng thứ ~i~ gồm ~2~ số nguyên ~u_i,\ v_i~ ~(1 \le u_i, v_i \le n,\ u_i \neq v_i)~ thể hiện có cạnh nối giữa đỉnh ~u_i~ và ~v_i~. Dữ liệu đảm bảo các cạnh tạo thành một cây.
Output
In ra một số nguyên duy nhất là chu vi của cây.
Sample 1
Input
1
Output
0
Sample 2
Input
3
3 2
2 1
Output
6
Sample 3
Input
5
4 2
1 4
5 4
3 4
Output
6
Comments
This comment is hidden due to too much negative feedback. Show it anyway.