{"code":"sumontree","name":"Tính tổng trên cây","description":"Cho cây $n$ đỉnh có gốc là $1$, mỗi đỉnh $u$ được cho các số $c_u, l_u, r_u$. Hãy tìm dãy $b_u$ sao cho gọi $a_u = \\sum b_v$ với $v$ là các đỉnh con của cây con gốc $u$ (tính cả $u$) thì $l_u \\le a_u\\le r_u$, và tổng $\\sum (b_u\\times c_u)$ là nhỏ nhất.\r\n\r\n##Input##\r\n\r\nDòng đầu chứa số $T$ là số lượng test:\r\n\r\n- Dòng đầu chứa số $n$ ($1\\le n\\le 10^5$)\r\n- Dòng hai chứa $n - 1$ số $p_2, p_3, ..., p_n$ với $p_u$ là cha của $u$ ($1 \\le p_u < u$)\r\n- Dòng ba chứa $n$ số $c_u$ ($1\\le c_u\\le 10^9$)\r\n- $n$ dòng tiếp theo mỗi dòng chứa hai số $l_u, r_u$ ($0\\le l_u\\le r_u\\le 10^9$)\r\n\r\nTổng $n$ của tất cả các test không vượt quá $10^5$.\r\n\r\n##Output##\r\n\r\nVới mỗi test ghi ra như sau: nếu có cách chọn dãy $b$\r\n\r\n- Dòng đầu ghi ra tổng nhỏ nhất tìm được\r\n- Dòng hai ghi ra $n$ số là dãy $b$ tìm được\r\n\r\nngược lại ghi ra $-1$ trên một dòng.\r\n\r\n##Ví dụ:##\r\n\r\n\r\n**Input 1:**\r\n\r\n    2\r\n    3\r\n    1 1\r\n    3 1 2\r\n    5 7\r\n    1 2\r\n    2 4\r\n    2\r\n    1\r\n    5 5\r\n    0 1\r\n    2 2\r\n    \r\n**Output 1:**\r\n\r\n    8\r\n    0 2 3 \r\n    -1\r\n    \r\n\r\n**Giải thích:**\r\n\r\n![enter image description here][1]\r\n\r\n\r\n  [1]: https://imgur.com/UjrPrQO.png","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}