409631: GYM103648 H Fledgling Fight

Albatross is a recent fledgling, looking to find a tree of her own to settle down in. As she scours the land, she finds the perfect tree to call her own.

As she approaches the tree, she sees $$$n$$$ different landing locations, connected to each other by $$$n-1$$$ branches. However, as she prepares to land on the tree, she quickly realizes something: this tree has already been claimed by Barbet, another fledgling! In fact, Barbet is very territorial, and he will fight Albatross for control of the tree.

Fledglings fight in a peculiar manner, by taking turns moving around the tree. In a fledgings turn, they must walk along a branch to an adjacent, unoccupied location on the tree. If a fledgling cannot make a move, then they lose the fight and lose ownership of the tree. The fight starts once a challenger fledgling (in this case, Albatross), lands on a tree, with the defender fledging (Barbet) making the first move.

Albatross has yet to pick a location on the tree to land on, but is suddenly worried: she doesn't know where Barbet is located! To complicate matters, both Albatross and Barbet are master logicians, so it may not even been worth fighting over this tree if Albatross will lose most of the time.

Can you figure out how many starting positions of Albatross and Barbet result in Albatross losing the fight?

The first line of input will contain a single integer, $$$2 \leq n \leq 2 \cdot 10^5$$$, denoting the number of locations on the tree.

Then, $$$n-1$$$ lines follow, each containing two integers $$$1 \leq a, b \leq n, a \not= b$$$, representing a branch between locations $$$a$$$ and $$$b$$$.

Output a single integer, representing the number of starting position pairs that end in Albatross losing.

3
1 2
2 3

2

4
1 2
1 3
1 4

6

Image courtesy of https://jspaint.app/ and a trackpad.