CF1029E Tree with Small Distances

• 87通过
• 179提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 动态规划,动规,dp 贪心 邻接表
• 难度 省选/NOI-
• 时空限制 1000ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

题目描述

给定一棵树。要求往树中加入一些边使得从1到其他节点的距离至多是2 。 输出加入边的最小数量。(边全部都是无向的)

输入格式

第一行一个整数n，表示树中的节点个数。 接下来n−1行，每行两个整数x,y,表示x,y之间有一条连边。

输出格式

输出一个整数，表示加入边的最小数量。

数据范围

对于30%的数据n≤10。对于70%的数据n≤100。对于100%的数据n≤105。

题目描述

You are given an undirected tree consisting of $n$ vertices. An undirected tree is a connected undirected graph with $n - 1$ edges.

Your task is to add the minimum number of edges in such a way that the length of the shortest path from the vertex $1$ to any other vertex is at most $2$ . Note that you are not allowed to add loops and multiple edges.

输入输出格式

输入格式：

The first line contains one integer $n$ ( $2 \le n \le 2 \cdot 10^5$ ) — the number of vertices in the tree.

The following $n - 1$ lines contain edges: edge $i$ is given as a pair of vertices $u_i, v_i$ ( $1 \le u_i, v_i \le n$ ). It is guaranteed that the given edges form a tree. It is guaranteed that there are no loops and multiple edges in the given edges.

输出格式：

Print a single integer — the minimum number of edges you have to add in order to make the shortest distance from the vertex $1$ to any other vertex at most $2$ . Note that you are not allowed to add loops and multiple edges.

输入样例#1： 复制
7
1 2
2 3
2 4
4 5
4 6
5 7

输出样例#1： 复制
2

输入样例#2： 复制
7
1 2
1 3
2 4
2 5
3 6
1 7

输出样例#2： 复制
0

输入样例#3： 复制
7
1 2
2 3
3 4
3 5
3 6
3 7

输出样例#3： 复制
1

说明

The tree corresponding to the first example: The answer is $2$ , some of the possible answers are the following: $[(1, 5), (1, 6)]$ , $[(1, 4), (1, 7)]$ , $[(1, 6), (1, 7)]$ .

The tree corresponding to the second example: The answer is $0$ .

The tree corresponding to the third example: The answer is $1$ , only one possible way to reach it is to add the edge $(1, 3)$ .

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。