Розфарбуй дерево#533

Розфарбуй дерево (Розбір)

Спершу з'ясуємо, які дерева взагалі допускають хоч одне коректне розфарбування.

Крок 1: не більше двох дітей. Діти вершини отримують суми s_v + 1 або s_v + 2 — лише два різні значення. Тому якщо в якоїсь вершини три і більше дітей, дві з них неминуче збігаються, і відповідь дорівнює нулю.

Крок 2: якщо розгалужень немає. Якщо дерево — просто шлях, то суми вздовж нього строго зростають, отже будь-яке розфарбування коректне, і відповідь дорівнює 2^n.

Крок 3: розгалуження мусять лежати на одному ланцюзі. Нехай і — дві вершини з двома дітьми, жодна з яких не є предком іншої. Тоді кожна з них породжує дві «гілки», суми яких мусять бути попарно різними; неважко переконатися, що двох значень і на це не вистачає, і відповідь нульова. Отже, всі вершини з двома дітьми мають утворювати ланцюг b_1, b_2, \ldots, b_r, де кожна наступна — нащадок попередньої.

Крок 4: бічні гілки — лише шляхи. Кожна «бічна» гілка (та, що відходить від b_i вбік і не веде до b_{i+1}) не має права розгалужуватися далі, інакше ми знову потрапляємо в ситуацію кроку 3.

Отже, допустиме дерево — це «хребет» від кореня, уздовж якого висить кілька бічних шляхів, а закінчується він вершиною з двома шляхами.

Підрахунок. Тепер порахуємо кількість розфарбувань як добуток незалежних множників.

Ділянка від кореня до b_1 нічого не обмежує (це просто шлях), тому дає 2^{\,\mathrm{depth}(b_1)} варіантів.

Дві гілки, що відходять від однієї вершини. Нехай від вершини відходять два кінцеві шляхи довжин і . Поки обидві гілки «живі», їхні суми зобов'язані чергуватися: якщо одна взяла s+1, друга мусить узяти s+2, далі перша — s+3 і так далі, тобто рух повністю визначений з точністю до вибору, хто йде першим. Свобода з'являється лише тоді, коли коротша гілка закінчилась і довша може рухатися вільно. Підрахунок дає

\mathrm{term}(a, b) = \begin{cases} 2, & a = b;\\ 3 \cdot 2^{\,|a-b|-1}, & a \ne b. \end{cases}

Бічна гілка проти продовження хребта. Якщо від b_i відходить бічний шлях довжини , а до наступного розгалуження b_{i+1} веде ділянка з ребер, то міркування те саме, але тепер бічна гілка мусить «вміститися»: при \gamma < \sigma розфарбувань немає. Отже,

\mathrm{cont}(\sigma, \gamma) = \begin{cases} 0, & \gamma < \sigma;\\ 1, & \gamma = \sigma;\\ 3 \cdot 2^{\,\gamma-\sigma-1}, & \gamma > \sigma. \end{cases}

Разом відповідь дорівнює

2 \cdot 2^{\,\mathrm{depth}(b_1)} \cdot \prod_{i=1}^{r-1} \mathrm{cont}(\sigma_i, \gamma_i) \cdot \mathrm{term}(\ell_1, \ell_2),

де \ell_1, \ell_2 — довжини двох кінцевих шляхів від останнього розгалуження, а зовнішня двійка — це вибір кольору кореня.

Реалізація: одним обходом знаходимо дітей і глибини, перевіряємо всі структурні умови, після чого множимо готові множники. Степені двійки за модулем 10^9+7 рахуємо заздалегідь. Складність — на тест.