女仆咖啡厅桌游吧
题目背景
小 v 带萌萌的妹妹去玩,妹妹想去女仆咖啡馆,小 v 想去桌游吧。
妹妹:“我问你个问题,答不对你就做我一天的奴隶,答对了就今天我就全部听你的。”
小 v :“全部都听!?”
妹妹:“嘻嘻嘻,你还是回答问题吧!”
于是小 v 为了自己一天的幸福,来向你求助。
题目描述
小 v 所在的世界被规划成了树形结构,每一个节点上都可以建一个女仆咖啡厅或者桌游吧或者什么都不建。在确定点 $1$ 为根节点之后,规划局要求:对于每一个非叶子的节点 $i$,设它子树(包括自己)中所有的女仆咖啡厅的数量为 $cafe_i$,桌游吧数目为 $table_i$,都有 $cafe_i=table_i$。
妹妹的问题是:这颗树最多能放多少个女仆咖啡厅。
输入输出格式
输入格式
输入的第一行是,一个正整数 $n$,表示世界节点数。
第 $2$ 至 $n$ 行,每行两个正整数 $u$,$v$,表示 $u$ 与 $v$ 间有一条边。
输出格式
只有一行,最多能放的女仆咖啡厅的个数。
输入输出样例
输入样例 #1
5
1 2
2 3
3 4
2 5
输出样例 #1
2
说明
#### 数据规模与约定
- 对于 $30\%$ 的数据,保证 $n\le20$。
- 对于 $100\%$ 的数据,保证 $1\le n\le10^5$,$1 \leq u, v \le n$。