洛谷P1922——女仆咖啡厅桌游吧

Posted by Ytoworld's Blog on June 20, 2017

女仆咖啡厅 and OI?

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

//yzyun一定会喜欢的吧==

@yzyun

哈哈哈哈哈啊哈哈哈

题目背景

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

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

小v:“全部都听!?”

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

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

题目描述

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

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

输入输出格式

输入格式: 第一行,一个正整数N

第二至N行,每行两个正整数ui,vi,表示vi,ui有一条边。

输出格式: 只有一行,最多能放的女仆咖啡厅的个数。

输入输出样例

输入样例#1: 5 1 2 2 3 3 4 2 5 输出样例#1: 2 说明

对于30%的数据,1<=N<=20

对于100%的数据,1<=N<=10^5

题目:https://www.luogu.org/problem/show?pid=1922