Balanced Tree Maid Cafe Maximization

In a world represented by a tree structure with node 1 as the root, each node can be configured as either a maid cafe, a board game bar, or nothing. For each non‐leaf node \(i\) (a node with at least one child), let \(cafe_i\) be the number of maid cafes and \(table_i\) be the number of board game bars in the subtree of \(i\) (including \(i\) itself). The planning department requires that

[ cafe_i = table_i ]

for every non‐leaf node \(i\). In other words, when we treat a maid cafe as contributing \(+1\) and a board game bar as \(-1\), the total sum of values within the subtree of every non‐leaf node must be zero. Note that leaf nodes do not have to satisfy any constraint and can be assigned arbitrarily.

Your task is to determine the maximum number of maid cafes (i.e. nodes assigned a value of +1) that can be placed in the tree while satisfying the above constraint.

inputFormat

The first line contains an integer \(n\) representing the number of nodes in the tree.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (\(1 \le u, v \le n\)) describing an edge between nodes \(u\) and \(v\). The tree is rooted at node 1.

outputFormat

Output a single integer, which is the maximum number of maid cafes that can be placed in the tree while satisfying the constraint.

sample

1

1