На початку гроші є лише у двох центральних банках, і вони сусідні, тож перший переказ іде рівно по одній дорозі. Далі відстань — діаметр множини непорожніх банків — лише зростає, бо жоден банк у нашому плані не спорожніє: кожен отримує рівно свою суму плюс усе, що має переслати далі.
Будуватимемо план так: заповнюємо банки по одному, завжди беручи сусідній до вже заповненої частини. Тоді заповнена частина завжди залишається зв'язним піддеревом, а відстані від нового банку до неї пробігають усі значення від до найбільшої — отже банк, віддалений від нового рівно на , завжди знайдеться, і саме він буде відправником.
Який саме банк заповнювати наступним? Придатні лише ті, для яких найдальший заповнений банк лежить на відстані щонайменше (інакше переказ до них уже неможливий, а надалі лише зростає). Серед придатних беремо той, у якого ця найдальша відстань найменша: тоді зростає якнайповільніше й решта банків лишаються досяжними.
Суми не обмежують нічого й рахуються наприкінці: пройдіть послідовність переказів у зворотному порядку, і кожен банк має отримати свій a_i плюс усе, що він перешле далі. Те, що лишилося в центральних банках, і є сумами, які вони друкують. Переказів виходить рівно n - 2, що вкладається в обмеження .
Відповідь impossible не потрібна: описана побудова працює для будь-якого дерева й будь-якої пари сусідніх центральних банків.
Складність: O(n^2) — обхід у ширину з кожного доданого банку.
Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.