Even Tree

Вам предоставлено дерево — связный граф без циклов. В дереве имеется N узлов, пронумерованных от 1 до N, с корнем в узле 1.

Ваша задача — определить, какое максимальное количество ребер можно удалить из дерева, чтобы получить лес, в котором каждый связанный компонент содержит четное число узлов.

Ограничения:

2 <= N <= 100

Обратите внимание: входное дерево всегда можно разделить на компоненты с четным числом узлов.

Реализация

python

from collections import defaultdict


def dfs(start: int) -> int:
    # (1)!
    ret = 1
    visited[start] = True
    for v in tree[start]:
        if v not in visited:
            ret += dfs(v)
    if ret % 2 == 0:
        cuts.append(start)
    return ret


def even_tree():
    # (2)!
    dfs(1)

1. Обход DFS

2. 2 1
   3 1
   4 3
   5 2
   6 1
   7 2
   8 6
   9 8
   10 8
   Убрав рёбра (1,3) и (1,6), мы получим желаемый результат 2