{"code":"2022usopengold3","name":"USACO 2022 US Open Contest, Gold, Balancing a Tree","description":"Nông dân John đã tiến hành một nghiên cứu về sự tiến hóa của các giống bò khác nhau. Kết quả là một cây có gốc với $N(1\\leq N\\leq 10^5)$ nút đánh số từ $1$ đến $N$, mỗi nút tương ứng với một giống bò. Với mỗi $i∈[2,N]$, nút cha của $i$ là nút $p_i$ $(1\\leq p_i <i)$, nghĩa là giống $i$ tiến hóa từ giống $p_i$. Nút $j$ được gọi là tổ tiên của nút $i$ nếu $j=p_i$ hoặc $j$ là tổ tiên của $p_i$.\r\n\r\nMỗi nút $i$ tương ứng với giống bò được gán số nguyên $s_i$. Sự \"mất cân bằng\" của cây là giá trị lớn nhất của $|s_i−s_j|$ trên tất cả các cặp nút $(i,j)$ với $j$ là tổ tiên của $i$.\r\n\r\nNông dân John không biết giá trị chính xác của $s_i$ của mỗi giống, nhưng ông biết giới hạn dưới và giới hạn trên của những giá trị này. Công việc của bạn là gán giá trị nguyên của $s_i∈[l_i,r_i]$ $(0 \\leq l_i \\leq r_i \\leq 10^9)$ cho mỗi nút sao cho sự mất cân bằng của cây là nhỏ nhất.\r\n#### Input\r\n- Dòng đầu tiên chứa số $T(1\\leq T \\leq 10)$ - số lượng test con, và số nguyên $B \\in (0,1)$.\r\n\r\n- Dòng đầu tiên của mỗi test chứa số $N$, sau đó là $N-1$ số nguyên $p_1,...p_N$.\r\n\r\n- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i,r_i$.\r\n\r\n- Dữ liệu đảm bảo tổng $N$ của tất cả các test không vượt quá $10^5$.\r\n\r\n#### Output\r\nVới mỗi test, in ra $1$ hoặc $2$ dòng, dựa vào giá trị của $B$:\r\n - Dòng đầu in ra độ mất cân bằng nhỏ nhất.\r\n - Nếu $B=1$, dòng thứ $2$ in ra $N$ số nguyên $s_1,...,s_N$ cách nhau bởi dấu cách.\r\n\r\n#### Scoring\r\n - Subtask $1$: $l_i=r_i$ với mọi $i$.\r\n - Subtask $2$: $p_i=i-1$ với mọi $i$. \r\n - Subtask $3$: Không có điều kiện gì thêm.\r\n \r\n Với mỗi subtask, nửa đầu sẽ có $B=0$, nửa sau sẽ có $B=1$.\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```\r\n        3 0\r\n        3\r\n        1 1\r\n        0 100\r\n        1 1\r\n        6 7\r\n        5\r\n        1 2 3 4\r\n        6 6\r\n        1 6\r\n        1 6\r\n        1 6\r\n        5 5\r\n        3\r\n        1 1\r\n        0 10\r\n        0 1\r\n        9 10\r\n        ```\r\n    ???+ \"Output\"\r\n        ```\r\n        3\r\n        1\r\n        4        \r\n        ```\r\n    ??? warning \"Note\"\r\n    \r\n        Đối với test đầu tiên, độ mất cân bằng nhỏ nhất là $3$. Một cách để đạt được là $[s_1,s_2,s_3]=[4,1,7]$.\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```\r\n        3 1\r\n        3\r\n        1 1\r\n        0 100\r\n        1 1\r\n        6 7\r\n        5\r\n        1 2 3 4\r\n        6 6\r\n        1 6\r\n        1 6\r\n        1 6\r\n        5 5\r\n        3\r\n        1 1\r\n        0 10\r\n        0 1\r\n        9 10\r\n        ```\r\n    ???+ \"Output\"\r\n        ```\r\n        3\r\n        3 1 6\r\n        1\r\n        6 5 5 5 5\r\n        4\r\n        5 1 9       \r\n        ```\r\n    ??? warning \"Note\"\r\n    \r\n        Đối với test đầu tiên, độ mất cân bằng nhỏ nhất là $3$. Một cách để đạt được là $[s_1,s_2,s_3]=[3,1,6]$.","points":1000.0,"partial":true,"time_limit":2.0,"memory_limit":262144,"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}}