AT_abc223_g [ABC223G] Vertex Deletion

给定一棵有 $N$ 个顶点的树。顶点编号为 $1,2,\ldots,N$，第 $i$ 条边（$1 \leq i \leq N-1$）连接顶点 $u_i$ 和顶点 $v_i$。 请计算满足以下条件的整数 $i\ (1 \leq i \leq N)$ 的个数： - 从原树中删除顶点 $i$ 及其所有相连的边后，得到的图的最大匹配数与原树的最大匹配数相等。

输入以如下格式从标准输入读入。 > $N$ > $u_1\ v_1$ > $u_2\ v_2$ > $\vdots$ > $u_{N-1}\ v_{N-1}$

输出答案。

## 限制条件 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq u_i < v_i \leq N$ - 给定的图是一棵树 - 输入均为整数 ## 样例解释 1 原树的最大匹配数为 $1$。删除顶点 $1$ 及其所有相连的边后，得到的图的最大匹配数为 $1$；删除顶点 $2$ 及其所有相连的边后，得到的图的最大匹配数为 $0$；删除顶点 $3$ 及其所有相连的边后，得到的图的最大匹配数为 $1$。因此，满足条件的 $i$ 有 $1,3$ 共 $2$ 个，应输出 $2$。 由 ChatGPT 4.1 翻译