#P1922. 女仆咖啡厅桌游吧

女仆咖啡厅桌游吧

题目背景

小 v 带萌萌的妹妹去玩,妹妹想去女仆咖啡馆,小 v 想去桌游吧。

妹妹:“我问你个问题,答不对你就做我一天的奴隶,答对了就今天我就全部听你的。”

小 v :“全部都听!?”

妹妹:“嘻嘻嘻,你还是回答问题吧!”

于是小 v 为了自己一天的幸福,来向你求助。

题目描述

小 v 所在的世界被规划成了树形结构,每一个节点上都可以建一个女仆咖啡厅或者桌游吧或者什么都不建。在确定点 11 为根节点之后,规划局要求:对于每一个非叶子的节点 ii,设它子树(包括自己)中所有的女仆咖啡厅的数量为 cafeicafe_i,桌游吧数目为 tableitable_i,都有 cafei=tableicafe_i=table_i

妹妹的问题是:这颗树最多能放多少个女仆咖啡厅。

输入格式

输入的第一行是,一个正整数 nn,表示世界节点数。

22nn 行,每行两个正整数 uuvv,表示 uuvv 间有一条边。

输出格式

只有一行,最多能放的女仆咖啡厅的个数。

5
1 2
2 3
3 4
2 5
2

提示

数据规模与约定

  • 对于 30%30\% 的数据,保证 n20n\le20
  • 对于 100%100\% 的数据,保证 1n1051\le n\le10^51u,vn1 \leq u, v \le n