Maximum Group of Pairwise Strangers in an Acquaintance Tree
Company: Two Sigma
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a social network of `n` people, labeled `0` through `n - 1`. For some pairs of people, it is known that the two people in the pair know each other. The "knows" relation is symmetric: if person `a` knows person `b`, then person `b` knows person `a`.
You are guaranteed that the graph built from these acquaintance relationships is a **tree**: it has exactly `n - 1` relationship pairs, and every person is connected to every other person through some chain of acquaintances.
Select the **maximum** number of people such that **no two selected people know each other** (i.e., no selected pair is directly connected by an acquaintance edge). Return that maximum count.
Write a function that takes:
- `n` — the number of people, and
- `edges` — a list of `n - 1` pairs `[a, b]` (with `0 <= a, b < n`, `a != b`), where each pair means person `a` and person `b` know each other,
and returns a single integer: the maximum number of people you can select so that no two of them know each other.
**Example 1**
```
n = 3
edges = [[0, 1], [0, 2]]
```
Output: `2`
Person `0` knows both `1` and `2`, but `1` and `2` do not know each other. Selecting `{1, 2}` gives 2 people who are pairwise strangers. Any set of 3 would have to include person `0` together with a neighbor, which is not allowed.
**Example 2**
```
n = 7
edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [5, 6]]
```
Output: `4`
One optimal selection is `{0, 3, 4, 5}`. Person `0` knows only `1` and `2`; person `3` and person `4` know only `1`; person `5` knows only `2` and `6`. No pair among `{0, 3, 4, 5}` is directly connected, so all four are pairwise strangers, and no valid selection of 5 people exists.
**Example 3**
```
n = 1
edges = []
```
Output: `1`
A single person trivially satisfies the condition.
**Constraints**
- `1 <= n <= 10^5`
- `edges.length == n - 1`
- The relationship graph is a connected tree (no cycles, no duplicate edges, no self-loops).
Your solution should run in `O(n)` time. In addition to the provided examples, you are expected to design your own test cases covering edge cases such as a single person, a path-shaped network, and a star-shaped network.