Maximum Tree Matching

Silver

15000ms500MB

You are given a tree with n nodes labeled 1 through n, described by its n - 1 edges (so n = edges.length + 1).

A matching is a set of edges in which no two edges share a node.

Return the maximum possible number of edges in a matching.

Examples

Example 1

Input: edges = [[1,2],[1,3],[3,4],[3,5]]
Output: 2
Explanation: The tree has 5 nodes. Edges [1,2] and [3,4] share no node, so
they form a matching of size 2. Any three edges would have to reuse a node —
node 1 or node 3 — so 2 is the maximum.

Example 2

Input: edges = [[2,1]]
Output: 1
Explanation: A single edge is itself a matching.

Constraints

$1 \leq$ n $\leq 2 \cdot 10^5$ where n = edges.length + 1
$1 \leq$ a, b $\leq$ n
The edges form a valid tree.

Examples

Example 1

Input

edges = [[1, 2], [1, 3], [3, 4], [3, 5]]

Output

Example 2

Input

edges = [[2, 1]]

Output

Loading editor...

Click "Run" to test with sample cases or "Submit" to run all tests.

Maximum Tree Matching

Silver

15000ms500MB

You are given a tree with n nodes labeled 1 through n, described by its n - 1 edges (so n = edges.length + 1).

A matching is a set of edges in which no two edges share a node.

Return the maximum possible number of edges in a matching.

Examples

Example 1

Input: edges = [[1,2],[1,3],[3,4],[3,5]]
Output: 2
Explanation: The tree has 5 nodes. Edges [1,2] and [3,4] share no node, so
they form a matching of size 2. Any three edges would have to reuse a node —
node 1 or node 3 — so 2 is the maximum.

Example 2

Input: edges = [[2,1]]
Output: 1
Explanation: A single edge is itself a matching.

Constraints

$1 \leq$ n $\leq 2 \cdot 10^5$ where n = edges.length + 1
$1 \leq$ a, b $\leq$ n
The edges form a valid tree.

Examples

Example 1

Input

edges = [[1, 2], [1, 3], [3, 4], [3, 5]]

Output

Example 2

Input

edges = [[2, 1]]

Output

Loading editor...

Click "Run" to test with sample cases or "Submit" to run all tests.