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