#P9449. [ICPC2021 WF] Take On Meme

[ICPC2021 WF] Take On Meme

题目描述

The Internet can be so fickle. You work for a small ad agency, Mimi's Mammoth Memes. Your ad campaigns are very cheap, and rely on the hope of producing the next hit viral meme. Unfortunately, the last four hundred or so memes have failed to take off, despite having been precisely engineered to appeal to every single person on Earth. You're not sure what exactly went wrong, but you've decided to try a new approach: crowd sourcing!

According to your scientific meme theory, all memes can be rated from -\infty to \infty on two scales: xanthochromism, and yellowishness, also known as (xx, yy) values. Obviously (you think), the best memes are memorable for being particularly xanthochromic, yellowish, unxanthochromic, or unyellowish. You feel that the "quality" of any meme is directly measurable as its squared Euclidean distance (x2+y2x^2 + y^2) from the Base Meme (00, 00), otherwise known as All Your Base.

To produce the ultimate viral meme, you'll be taking your company's last few failed memes and throwing them into a tournament, decided by online voting. The tournament can be represented as a rooted tree. Input memes come in at the leaves, and at each internal node, a vote will be held among its kk child memes (x1x_1, y1y_1), \ldots, (xkx_k, yky_k). After the vote, all the memes will be horrifically mangled and merged into a brand new meme, specifically calculated to emphasize the winner and de-emphasize all the losers: the resultant xx value will be $$ \sum_{i=1}^{k} w_i \cdot x_i, $$ where wiw_i is 11 if the ithi^{th} child won, and 1-1 otherwise. The yy value is computed similarly. This new meme will move on to the next vote in the tournament - or, if there is no parent, it will be declared the champion and the ultimate meme!

You already have the structure of the tournament planned out, including all the input memes and the internal voting nodes. What is the largest possible quality for any meme that the tournament could produce?

输入格式

The first line of input contains an integer nn (1n1041 \leq n \leq 10^4), giving the total number of nodes in the tournament tree. The next nn lines each describe a single tree node indexed from 11 to nn. The line for node ii starts with an integer kik_i (0ki1000 \leq k_i \leq 100), the number of children of that node. If kik_i is 00, then node ii is an input meme and there will be two more integers xix_i and yiy_i (103xi,yi103-10^3 \leq x_i, yi \leq 10^3) describing it. If k_i > 0, then kik_i different integers jj (i < j \leq n) will follow, giving the indices of the kik_i nodes entering this voting step.

All input memes will eventually be merged into the final output meme at node 11. The complete tree will have a height of no more than 1010.

输出格式

Output the largest possible quality for the champion meme at node 11.

4
3 2 3 4
0 10 1
0 3 6
0 2 7

169
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