背景

译自 Northwestern Europe Regional Contest (NWERC) 2022 Problem H。

原题许可协议为 CC BY-SA。

题目描述

二叉搜索树是计算机科学中最有用的数据结构之一。许多方法可以保持它们平衡，例如使用树旋转（如 AVL 树）或随机化（如 treap）。这些方法有一个共同点：它们都在一定程度上又慢又复杂。

但这一切马上就要改变了！计算机科学家 Rob 发明了一种保持有根二叉树平衡的新方法，它比目前最先进的方法好得多。核心思想是反复执行一种 Rob 称为 robbery 的操作。一次 robbery 就是从树中取走一个叶子并删除它。只要在合适的时机应用 robbery，Rob 就能够以 $\mathcal{O}(1)$ 均摊时间保持树的平衡。

有人批评 Rob 的革命性发现，认为从树里删除元素会让算法不正确。Rob 并不同意这是个大问题；如果你计划存储 $2\cdot 10^5$ 个数，可能并不需要全部保留。但 Rob 接受了这一批评，并决定找到一种方法，使 robbery 的次数尽可能少。

:::align{center}

:::

图：样例输入 2 的示意图。删除红色标记的三个顶点（$4$、$5$ 和 $10$）后，树会变成强平衡；这是使树强平衡所需删除的最少顶点数。

给定一棵包含 $n$ 个顶点的有根二叉树。顶点编号为 $1$ 到 $n$，顶点 $1$ 是根。你的任务是求出使这棵树变为强平衡所需的最少 robbery 次数。

强平衡的含义是：它的所有子树都是平衡的。一棵有根二叉树称为平衡，当且仅当它的左子树和右子树深度之差至多为 $1$。回忆一下，robbery 只是取走一个叶子并删除它，而这样做可能会让它的父节点变成叶子。

输入格式

输入包含：

• 一行一个整数 $n$（$1 \leq n \leq 2\cdot 10^5$），表示树的顶点数。
• 接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$（$1 \leq u,v \leq n$，$u\neq v$），表示顶点 $u$ 和顶点 $v$ 之间有一条边。

保证给定边构成一棵以顶点 $1$ 为根的合法二叉树。不过，边可以以任意顺序出现，并且不是有向边：$u$ 可以是 $v$ 的父节点，也可以反过来。

输出格式

输出为了使树强平衡而需要删除的最少叶子数量。

6
1 2
1 3
3 4
3 5
5 6

1

12
1 2
2 3
3 4
3 5
1 6
6 7
7 8
7 9
9 10
6 11
11 12

3

提示

【数据规模与约定】

对于所有数据，满足 $1 \leq n \leq 2\cdot 10^5$；输入边构成以 $1$ 为根的合法二叉树；边无向给出且顺序任意。