2020牛客国庆集训派对day3 Points

Points

题目描述

Jack and Rose are playing games after working out so many difficult problems. They together drew a “Haizi” tree to show their collaboration. “Haizi” tree is the same as the tree defined in graph theory.

Now Jack would like to count the number of vertices whose degree is one in this tree. You need to help him with this calculation.

\textit{Degree}Degree: The degree of a vertex of a graph is the number of edges that are connected with the vertex.

输入描述:

The first line contains an integer {n}n (2 \leq n \leq 10^52≤n≤10 5 ) — the number of vertices. The next {n-1}n−1 lines describe the edges of the tree, where the {i}i-th line contains two integers x_i≤n) — the two vertices that is connected by the {i}i-th edge.

输出描述:

Output one integers in one line — the number of vertices whose degree is one. 示例1 输入 复制

5 1 2 2 3 1 4 4 5

输出 复制

2

说明 As shown in figure below, only the vertex {3}3 and vertex {5}5 are connected with only one edge. So there are {2}2 vertices whose degree is one.

题解：

题目很简单就是问度为1的点有多少？ 每输入一个边，就让两个点的度数+1，最后记录有多少点的度数为1

代码：

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+8; int odd[maxn]; int main() { int n; cin>>n; for(int i=1;i<n;i++) { int x,y; cin>>x>>y; odd[x]++; odd[y]++; } int sum=0; for(int i=1;i<=n;i++) { if(odd[i]==1)sum++; } cout<<sum; return 0; }