B. Наибольшее паросочетание в дереве

2000 мс · 256 МБ · всё или ничего

Паросочетание - множество рёбер, попарно не имеющих общих вершин. Найдите наибольшее по количеству рёбер паросочетание дерева.

Состояние - «вершина, занята ли она уже ребром паросочетания вниз»:

dp[v][0] = \sum_c \max(dp[c][0], dp[c][1])

dp[v][1] = dp[v][0] + \max_c \bigl( dp[c][0] + 1 - \max(dp[c][0], dp[c][1]) \bigr)

Вторая формула читается так: берём базовый ответ, выбираем одного ребёнка $c$ , к которому проведём ребро паросочетания, и заменяем его вклад: вместо $\max(dp[c][0], dp[c][1])$ теперь $dp[c][0] + 1$ - ребёнок обязан быть свободен, зато добавилось ребро.

Такая замена «вычесть старый вклад, прибавить новый» - стандартный приём, когда надо выбрать ровно одного ребёнка. Он работает, потому что сумма обратима.

Ответ - $\max(dp[\text{корень}][0], dp[\text{корень}][1])$ .

Формат ввода

В первой строке - число $n$ ( $1 \le n \le 10^5$ ).

В следующих $n - 1$ строках - рёбра дерева.

Формат вывода

Одно число - размер наибольшего паросочетания.

Примеры

ввод

вывод

ввод

3
1 2
1 3

вывод

Войдите, чтобы отправлять решения.