#z116. 树的最大独立集-家族聚会

树的最大独立集-家族聚会

题目描述
家族中有一棵由N个节点组成的树,每个节点代表一位家庭成员。现在要邀请尽可能多的家庭成员参加聚会,但任何两个直接相连的家庭成员(即父子关系)不能同时被邀请。求最多能邀请多少人?

输入
第一行包含整数N(1 ≤ N ≤ 100000),表示树的节点数。
接下来N-1行,每行包含两个整数u和v(1 ≤ u, v ≤ N),表示节点u和v之间有一条边。

输出
输出一个整数,表示最多能邀请的人数。

样例
输入:

5  
1 2  
1 3  
2 4  
2 5  

输出:

3