#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