树上关灯

题目描述

小红得到一棵节点数为 $n$ 的树，树上每个节点都有一盏初始状态为“开启”的灯。小红每次操作可改变相邻两盏灯的状态（开变关，关变开） ，她希望通过操作使树上不存在两盏相邻的灯同时处于开启状态，求至少需要操作的次数。树上两个节点相邻当且仅当它们之间有边相连。

输入格式

1. 第一行输入一个正整数 $n$（$1\leq n\leq 10^5$ ），表示树的节点数量。
2. 接下来 $n - 1$ 行，每行输入两个正整数 $u, v$（$1\leq u, v\leq n$ ），表示节点 $u$ 和节点 $v$ 相邻。

输出格式

输出一个正整数 $k$ ，代表使树上不存在相邻开启灯时操作的最小次数。

输入输出样例

输入样例 1

6
1 2
1 3
1 4
4 5
4 6

输出样例 1

1

样例 1 说明

只需要操作1次，对1和4号节点操作，它们的灯均被关闭，此时不存在两个相邻的灯同时开启。