Розбір

Помітимо, що країна утворює граф (міста "— вершини, дороги "— ребра). Для початку побудуємо мінімальне остове дерево цього графа, назвемо його MST. Правильна послідовність додавання ребер існує тоді і тільки тоді, коли сума цін усіх ребер MST менша за загальну кількість копійок у країні або рівна цій кількості. Якщо сума цін ребер більша за загальну кількість, то твердження, очевидно, виконується(ми не можемо заплатити за побудову всіх ребер MST).

Покажемо, що якщо сума менша за загальну кількість або рівна їй, то в такому MST завжди існуватиме ребро, яке можна побудувати. Якщо б це було не так, то виконувалася б нерівність $w_i>c_{v_i}+c_{u_i}$(ціна ребра більша за суму кількостей копійок у вершинах, які воно з'єднує) для кожного ребра MST. А з цих нерівностей випливає, що сума цін усіх доріг більша за загальну кількість копійок($w_i,c_{v_i},c_{u_i}>0$), що суперечить умові.

MST, у якому додається ребро $i$, ми перетворюємо на інший, де замість вершин $v_i$ та $u_i$ вже одна вершина з кількістю копійок, рівною $c_{v_i}+c_{u_i}-w_i$, а також до неї проведені всі ребра, інцидентні до вершин $v_i$ та $u_i$. Така побудова, по суті, просто поєднує вершини сусіди у групи. При цьому різниця між сумою цін ребер MST та загальною кількістю копійок не змінилася, тому ми завжди зможемо знайти ребро, яке можна побудувати.

За допомогою цих умов досить легко написати розв'язок за $O(n^2)$: будуємо MST, а потім $n-1$ разів шукаємо ребро яке можна було б побудувати.

Для розв'язку за $O(n)$ будемо шукати потрібну послідовність ребер за допомогою пошуку у глибину. Запускаємо dfs з будь-якої вершини графу. В dfs ми для кожної вершини $v$ перебираємо сина вершини $v$, запускаємо dfs від сина, а потім намагаємося побудувати ребро між $v$ і сином. Якщо ребро не можна будувати, ми додаємо сина до певного стека і запам'ятовуємо для сина те ребро, яке його поєднує з $v$ (батьком). Потрібно зазначити, що оскільки ребро не можна побудувати, то його побудова зменшує сумарну кількість монет групи. Після проходження всіх синів вершини $v$ ми робимо наступне: доки остання вершина $s$ стеку лежить у піддереві вершини $v$ і доки ми можемо об'єднувати $s$ та $v$, ми їх об'єднуємо і видаляємо $s$ зі стека (ми пам'ятаємо ребро, що веде від $s$ до його батька, а всі вершини на шляху між $v$ та $s$ уже об'єднані з $v$ через властивості стеку). Через те, що сума цін ребер менша за загальну кількість монет або рівна їй, після dfs-обходу всі $n-1$ дороги будуть побудовані.