Кожен маршрут гладкий тоді й лише тоді, коли на всіх дорогах однакова кількість вибоїн. Якщо всі кількості рівні, AND і OR кожного маршруту збігаються. Навпаки, візьмемо дві дороги і . Видалення розбиває дерево на дві частини; нехай — кінець у частині без , і симетрично визначимо для . Маршрут від до містить і , і . AND дорівнює OR на маршруті тоді й лише тоді, коли кожен біт однаковий на всіх його дорогах, тож кількості вибоїн на і рівні.
Біти незалежні. Операція змінює лише біт , тому кожен біт розв'язуємо окремо: оберемо цільове значення c \in \{0, 1\} біта , і нехай — множина доріг, у яких біт відрізняється від . Маршрути для біта мають змінити рівно дороги з , тобто їхня симетрична різниця має дорівнювати .
Вартість дорівнює , де — кількість міст із непарною кількістю доріг з (вона парна за лемою про рукостискання). Нижня оцінка: маршрут змінює парність степеня лише двох своїх кінців, тож кожне непарне місто є кінцем якогось маршруту, і потрібно щонайменше маршрутів. Верхня оцінка: довільно розіб'ємо непарні міста на пари й візьмемо маршрути між парами. Їхня симетрична різниця має ті самі непарні міста, що й . У дереві це визначає множину: дорога належить (або ) тоді й лише тоді, коли частина з одного її боку містить непарну кількість непарних міст, бо сума степенів у цій частині дорівнює подвоєній кількості внутрішніх доріг плюс один за саму дорогу, якщо вона належить множині. Отже, P = S.
Підрахунок. Нехай X_v — XOR кількостей вибоїн на дорогах при місті , а d_v — його степінь. Для цілі c = 0 парність в — це біт числа X_v; для c = 1 — цей біт XOR (d_v \bmod 2). Підрахувавши ці парності за всіма містами, отримаємо \mathrm{odd}_c(i) = \mathrm{odd}(S) для обох цілей, і відповідь дорівнює
Старші біти дорівнюють на всіх дорогах і нічого не коштують. Складність — O(30 \cdot n) на тестовий випадок.