Что означает n0 k0 в алгоритме Kingdom Division hackerrank?

Question

[Ирина Грачева]

https://www.hackerrank.com/challenges/kingdom-divi...
У короля Артура большое королевство, которое можно представить в виде дерева, где узлы соответствуют городам, а ребра соответствуют дорогам между городами. В королевстве всего городов, пронумерованных от до n

Король хочет разделить свое королевство между двумя своими детьми, Реджи и Бетти, дав каждому из них или больше городов; однако они не ладят, поэтому он должен разделить королевство таким образом, чтобы они не вторгались в города друг друга. Первый брат вторгнется в город второго брата, если у второго брата нет других городов, напрямую связанных с ним.

Я решил задачу. Мое решение: https://codefile.io/f/oaCwLAeX0t

Но я не понимаю алгоритм выше, так как он совсем другой.

Код:

#!/bin/python3

import sys

def count(tree):
    stack = [ i for i in range(len(tree)) if len(tree[i][1]) == 1 ]
    ret = None
    while stack:
        icur = stack.pop()
        cur = tree[icur]
        tree[icur] = None
        if cur is not None and cur[1]:
            inext = cur[1][0]
            next = tree[inext]
            next[1].remove(icur)
            n0, k0 = next[0]
            n1, k1 = cur[0]
            next[0] = ( ((n0 + k0) * (n1 + k1) + n0 * n1) // 2, k0 * n1 // 2 )
            if len(next[1]) == 1:
                stack.append(inext)
            elif not next[1]:
                ret = next[0][0]
    return ret

mod = 10 ** 9 + 7

n = int(input().strip())

tree = [ [(0, 2), []] for _ in range(n) ]

for a0 in range(n - 1):
    u, v = input().strip().split(' ')
    u, v = int(u), int(v)
    u -= 1
    v -= 1
    tree[u][1].append(v)
    tree[v][1].append(u)

print(count(tree) % mod)

Вход:

5
1 2
1 3
3 4
3 5

Выход: 4

Какая цель n0 k0 как индексa 0 "next"? Как он используется? В чем идея алгоритма?

Answer 1

[Wataru]

Тут считаются 2 динамических программирования: 1) Сколько вариантов раскрасить поддерево так, что ни одна вершина не изолирована. 2) Сколько вариантов раскрасить поддерево так, что ни одна вершина кроме корня не изолирована, а корень изолирован.

Считается снизу вверх, в "стеке" получаются вершины для которых значения уже подсчитаны - изначально листья. n, k - это как раз значения ДП в текущей вершине и в отце. текущей вершины.

В структуре tree для каждой вершины хранится 2 объекта. Под индексом 0 - пара значений дп, под индексом 1 - список соседей в дереве.

next получается значение этой структуры для отца, cur - для текущей вершины.