trang chủ / đề bài / icpcwf21_k

Đó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ị (x,y). 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 x2+y2 từ meme đó tới Meme Gốc (0,0).

Để 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 k meme con (x1,y1),…,(xk,yk) 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ị x mới là

∑i=1kwi·xi,

trong đó wi=1 nếu meme con thứ i thắng và wi=−1 nếu ngược lại (mỗi cuộc bình chọn có đúng một meme thắng). Giá trị y đượ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 n, tổng số nút của cây giải đấu.
  • n dòng tiếp theo, mỗi dòng mô tả một nút, các nút được đánh số từ 1 đến n. Dòng của nút i bắt đầu bằng số nguyên ki, số con của nút đó.
    • Nếu ki=0 thì nút i là một meme đầu vào, theo sau là hai số nguyên xi và yi mô tả meme đó.
    • Nếu ki>0 thì theo sau là ki số nguyên j đôi một khác nhau (i<j≤n), chỉ số của ki 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 1.

Dữ liệu ra

In ra chất lượng lớn nhất có thể của meme vô địch ở nút 1.

Ràng buộc

  • 1≤n≤104.
  • 0≤ki≤100.
  • −103≤xi,yi≤103.
  • Các nút tạo thành một cây có gốc là nút 1, chiều cao của cây không quá 10.

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 1 có ba meme con (10,1), (3,6), (2,7). Nếu (10,1) thắng, meme vô địch là (10−3−2,1−6−7)=(5,−12) với chất lượng 25+144=169. Hai lựa chọn còn lại cho (−9,−2) và (−11,0), chất lượng 85 và 121.
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 2 cho nút 3 thắng: (−3−1,9−4)=(−4,5). Ở nút 5 cho nút 6 thắng: (1+3,4+1)=(4,5). Ở nút 1 cho nút 4 thắng: (−5+4−4,−7−5−5)=(−5,−17), chất lượng 25+289=314.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0