Đón đầu meme
Đề bài
Mô tả
Internet thật thất thường. Bạn làm việc cho một công ty quảng cáo nhỏ, Mimi's Mammoth Memes. Các chiến dịch quảng cáo của công ty rất rẻ và chỉ trông chờ vào hy vọng tạo ra meme lan truyền tiếp theo. Không may, khoảng bốn trăm meme gần nhất đều thất bại, dù đã được thiết kế chính xác để hấp dẫn từng người trên Trái Đất. Bạn không chắc điều gì đã sai, nhưng bạn quyết định thử một cách mới: huy động đám đông!
Theo lý thuyết meme khoa học của bạn, mọi meme đều được chấm điểm từ đến trên hai thang đo: độ vàng hóa (xanthochromism) và độ hơi vàng (yellowishness), còn gọi là giá trị . Hiển nhiên (bạn nghĩ vậy), những meme hay nhất là những meme đáng nhớ vì đặc biệt vàng hóa, hơi vàng, không vàng hóa hoặc không hơi vàng. Bạn cho rằng "chất lượng" của một meme đo trực tiếp được bằng bình phương khoảng cách Euclid từ meme đó tới Meme Gốc .
Để tạo ra meme lan truyền tối thượng, bạn sẽ đưa những meme thất bại gần đây của công ty vào một giải đấu được quyết định bằng bình chọn trực tuyến. Giải đấu được biểu diễn bằng một cây có gốc. Các meme đầu vào nằm ở các lá; tại mỗi nút trong, một cuộc bình chọn được tổ chức giữa meme con của nút đó. Sau bình chọn, mọi meme bị cắt xén và trộn thành một meme hoàn toàn mới, được tính để làm nổi bật meme thắng và làm mờ các meme thua: giá trị mới là
trong đó nếu meme con thứ thắng và nếu ngược lại (mỗi cuộc bình chọn có đúng một meme thắng). Giá trị được tính tương tự. Meme mới này đi tiếp vào cuộc bình chọn kế tiếp của giải đấu, hoặc, nếu nút không có cha, nó được tuyên bố là nhà vô địch, meme tối thượng!
Bạn đã lên sẵn cấu trúc giải đấu, gồm mọi meme đầu vào và mọi nút bình chọn. Hỏi chất lượng lớn nhất có thể của meme vô địch mà giải đấu có thể tạo ra là bao nhiêu?
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên , tổng số nút của cây giải đấu.
- dòng tiếp theo, mỗi dòng mô tả một nút, các nút được đánh số từ đến . Dòng của nút bắt đầu bằng số nguyên , số con của nút đó.
- Nếu thì nút là một meme đầu vào, theo sau là hai số nguyên và mô tả meme đó.
- Nếu thì theo sau là số nguyên đôi một khác nhau (), chỉ số của nút tham gia cuộc bình chọn này.
Mọi meme đầu vào cuối cùng đều được trộn vào meme vô địch ở nút .
Dữ liệu ra
In ra chất lượng lớn nhất có thể của meme vô địch ở nút .
Ràng buộc
- .
- .
- .
- Các nút tạo thành một cây có gốc là nút , chiều cao của cây không quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 3 2 3 4 0 10 1 0 3 6 0 2 7 |
169 | Nút có ba meme con , , . Nếu thắng, meme vô địch là với chất lượng . Hai lựa chọn còn lại cho và , chất lượng và . |
| 8 3 4 2 5 2 3 8 0 -3 9 0 -5 -7 2 6 7 0 1 4 0 -3 -1 0 1 4 |
314 | Ở nút cho nút thắng: . Ở nút cho nút thắng: . Ở nút cho nút thắng: , chất lượng . |
Bình luận