AT_abc223_g.[ABC223G] Vertex Deletion

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一棵有 $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}$

输出格式

输出答案。

输入输出样例

输入#1
```
3
1 2
2 3
```
输出#1
```
2
```
输入#2
```
2
1 2
```
输出#2
```
0
```
输入#3
```
6
2 5
3 5
1 4
4 5
4 6
```
输出#3
```
4
```

说明/提示

限制条件

$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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页