← 返回 twosigma 的题目列表Maximum Independent Set in a Tree
类型：online_judge
Given an undirected graph representing a relationship network that forms a tree, write a program to find the maximum number of people that can be chosen such that none of them are directly acquainted with each other.
Input:
The first line contains an integer $n$, representing the number of nodes (people).
The next $n-1$ lines each contain two integers $u$ and $v$, indicating an edge between nodes $u$ and $v$.
Output:
Print an integer, the maximum number of people that can be chosen.
Example:
Input:
5
1 2
1 3
2 4
3 5
Output:
3
Constraints: $n$ is in the range $1 \leq n \leq 10^5$.
Example
Input
5
1 2
1 3
2 4
3 5