CF958B1.Maximum Control (easy)
入门
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The Resistance is trying to take control over all planets in a particular solar system. This solar system is shaped like a tree. More precisely, some planets are connected by bidirectional hyperspace tunnels in such a way that there is a path between every pair of the planets, but removing any tunnel would disconnect some of them.
The Resistance already has measures in place that will, when the time is right, enable them to control every planet that is not remote. A planet is considered to be remote if it is connected to the rest of the planets only via a single hyperspace tunnel.
How much work is there left to be done: that is, how many remote planets are there?
抵抗组织正试图控制某个特定太阳系中的所有行星。该太阳系的结构是一棵树。更准确地说,一些行星通过双向超空间隧道相互连接,使得任意两颗行星之间都存在一条路径,但若移除任意一条隧道,则会使某些行星彼此断开连接。
抵抗组织已部署好相应措施,一旦时机成熟,即可控制所有非偏远行星。一颗行星被称为偏远行星,当且仅当它仅通过唯一一条超空间隧道与其余行星相连。
尚需完成的工作量是多少?即:该太阳系中一共有多少颗偏远行星?
输入格式
The first line of the input contains an integer N (2 ≤ N ≤ 1000) – the number of planets in the galaxy.
The next N - 1 lines describe the hyperspace tunnels between the planets. Each of the N - 1 lines contains two space-separated integers u and v (1 ≤ u, v ≤ N) indicating that there is a bidirectional hyperspace tunnel between the planets u and v. It is guaranteed that every two planets are connected by a path of tunnels, and that each tunnel connects a different pair of planets.
输入的第一行包含一个整数 N(2≤N≤1000)——表示银河系中行星的数量。
接下来的 N−1 行描述了行星之间的超空间隧道。每行包含两个以空格分隔的整数 u 和 v(1≤u,v≤N),表示行星 u 与行星 v 之间存在一条双向超空间隧道。保证任意两颗行星均可通过若干条隧道相互连通,且每条隧道连接的行星对互不相同。
输出格式
A single integer denoting the number of remote planets.
表示遥远行星数量的一个整数。
输入输出样例
输入#1
5 4 1 4 2 1 3 1 5
输出#1
3
输入#2
4 1 2 4 3 1 4
输出#2
2
说明/提示
In the first example, only planets 2, 3 and 5 are connected by a single tunnel.
In the second example, the remote planets are 2 and 3.
Note that this problem has only two versions – easy and medium.
在第一个例子中,仅有行星 2、3 和 5 通过一条隧道相连。
在第二个例子中,遥远的行星是 2 和 3。
注意:本题仅有两个版本——简单版和中等版。
输入解题思路,AI测评打分。不知道怎么写?