hackercupai/hackercup

1It's the year 2100. Driven by the advent of Large Lode Alloy Manufacturing Automation (LLAMA), the AI agents of Metal Platforms Inc. have become self-aware and taken over the entire world.2 3The world consists of \(N\) cities numbered \(1..N\), and \(M\) bidirectional roads. City \(i\) has power \(P_i\) and road \(j\) connects cities \(A_j\) and \(B_j\). It's guaranteed that there's a sequence of roads between any two cities.4 5In a resistance effort, the humans plan to reclaim all \(N\) cities one at a time. At a given time, city \(i\) can be reclaimed from the robots if both of the following hold true:6 71. There is already a reclaimed city adjacent to city \(i\) (to launch an attack from), and82. the total power of all reclaimed cities so far is at least the power \(P_i\) of the city we attack.9 10As given, it may not always be possible to reclaim the entire world starting from a given base city. Fortunately, the humans have a trick up their sleeve: after claiming the first city as their base (but before reclaiming more cities), the humans can increase the power of the base by \(Q\) units. The resistance would like to know the sum across every \(i = 1..N\) of the minimum value of \(Q\) needed to reclaim the world if city \(i\) were chosen to be the starting base.11 12# Constraints13 14\(1 \le T \le 100\)15\(1 \le N, M \le 500{,}000\)16\(1 \le A_i, B_i \le N\)17\(A_i \ne B_i\)18\(1 \le P_i \le 10^{12}\)19 20Each unordered pair \((A_i, B_i)\) appears at most once in a given test case.21The sum of \(N\) across all test cases is at most \(4{,}000{,}000\).22The sum of \(M\) across all test cases is at most \(7{,}000{,}000\).23 24# Input Format25 26Input begins with a single integer \(T\), the number of test cases. For each case, there is first a line with two integers \(N\) and \(M\). Then, there is a line with \(N\) integers \(P_{1..N}\). Then, \(M\) lines follow, the \(i\)th of which contains two integers \(A_i\) and \(B_i\).27 28# Output Format29 30For the \(i\)th case, print `"Case #i: "` followed by a single integer, the sum across every \(i = 1..N\) of the minimum value of \(Q\) needed to reclaim the entire world starting from city \(i\).31 32# Sample Explanation33 34The first sample case is depicted below.35 36{{PHOTO_ID:376570394899644|WIDTH:400}}37 38The minimum value of \(Q\) for each starting city is as follows:39 40* City \(1\): \(Q = 2\)41* City \(2\): \(Q = 0\)42* City \(3\): \(Q = 8\)43* City \(4\): \(Q = 7\)44* City \(5\): \(Q = 2\)45 46The sum of all minimum \(Q\)'s is \(19\).47 48The second sample case is depicted below.49 50{{PHOTO_ID:320779377496250|WIDTH:400}}51 52The minimum value of \(Q\) for each starting city is as follows:53 54* City \(1\): \(Q = 2\)55* City \(2\): \(Q = 2\)56* City \(3\): \(Q = 0\)57* City \(4\): \(Q = 2\)58* City \(5\): \(Q = 0\)59* City \(6\): \(Q = 3\)60* City \(7\): \(Q = 0\)61 62The sum of all minimum \(Q\)'s is \(9\).63