Problem1522--树-节点-连边

1522: 树-节点-连边

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

给定一个n 个点的树，在树上选出最多的点使得没有两个选出的点之间有连边。

Input

第一行一个整数n。
接下来n-1 行，每行两个正整数a b，表示有一条无向边连接标号为a b 的两个节点。

Output

输出一行一个整数，表示能够选出的最多的点数。

Sample Input Copy 

5
1 2
2 3
1 4
4 5

Sample Output Copy 

3

HINT

对于40% 的测试数据满足n<=10。
对于70% 的测试数据满足n<=1000。
对于100% 的测试数据满足n<=100000。

Source/Category

Peter9年级 
[Submit] [Status]