#855. COLORING - Tô màu cho cây

Cho đồ thị dạng cây gồm đỉnh, các đỉnh được đánh số từ đến . Đầu tiên, tất cả các đỉnh đều có màu trắng. Lần đầu tiên, bạn được chọn bất kì một đỉnh sau đó tô nó thành màu đen, các lượt chơi tiếp theo bạn phải chọn một đỉnh kề với đỉnh màu đen và tô nó thành màu đen. Trò chơi kết thúc khi tất cả các đỉnh đều được tô màu đen.

Mỗi lượt chơi, bạn nhận được số điểm bằng số đỉnh trắng liên thông với đỉnh đã chọn (tính cả đỉnh được chọn). Sau khi cộng điểm thì các cạnh liên thuộc với đỉnh màu đen bị xóa khỏi cây. Hỏi tổng số điểm lớn nhất bạn có thể nhận được là bao nhiêu?

Dữ liệu vào:

• Dòng đầu tiên ghi số là số đỉnh của cây;
• Dòng tiếp theo có số thể hiện có đường đi từ đỉnh đến với ( thì đỉnh là gốc cây).

Dữ liệu ra:

• Ghi ra một số duy nhất là tổng số điểm lớn nhất.

Ví dụ:

Dữ liệu vào:

14
0 1 1 1 2 2 3 4 4 4 5 5 7 7

Dữ liệu ra:

67

Dữ liệu vào:

5
0 1 1 2 2

Dữ liệu ra:

14

Giới hạn:

• .