题目背景

小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

思路:树形DP。因为每一个非叶子结点的子树的状态都是唯一的确定的,所以只需要把某个节点的儿子中叶子节点的个数统计出来。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100010
using namespace std;
int n,m,tot;
int dad[MAXN],f[MAXN];
int size[MAXN],num[MAXN];
int to[MAXN*],net[MAXN*],head[MAXN];
void add(int u,int v){
to[++tot]=v;net[tot]=head[u];head[u]=tot;
to[++tot]=u;net[tot]=head[v];head[v]=tot;
}
void dfs(int now){
size[now]=;
for(int i=head[now];i;i=net[i])
if(to[i]!=dad[now]){
dad[to[i]]=now;
dfs(to[i]);
if(size[to[i]]==) num[now]+=;
else f[now]+=f[to[i]];
size[now]+=size[to[i]];
}
f[now]+=(num[now]+)/;
}
int main(){
scanf("%d",&n);
for(int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
dfs();
cout<<f[];
}

最新文章

  1. Ruby类的继承
  2. 纪念逝去的岁月——C/C++选择排序
  3. Windows下gvim配置
  4. 理解LoadRunner中的局部变量和全局变量
  5. matlab report generator
  6. Eclipse4.4安装旧版本插件报错 Failed to prepare partial IU
  7. AngularJs 如何监视外部变量是否改变? 如何使用$cookieStore保存cookie?
  8. PHP5.3 里面数组的的实现方式
  9. pureMVC简单示例及其原理讲解一(开篇)
  10. Codeforces 821E Okabe and El Psy Kongroo
  11. 常用 Git 命令清单
  12. 46. Permutations(medium, backtrack, 重要)
  13. C++ 类的静态成员变量及静态成员函数
  14. CodeForces - 616F:Expensive Strings (后缀自动机)
  15. ORACLE中的FTP例子代码
  16. 第7月第26天 iOS httpserver
  17. [Functional Programming] mapReduce over Async operations and fanout results in Pair(rejected, resolved) (fanout, flip, mapReduce)
  18. Mongodb 与 Mongoose 的使用
  19. php程序中判断session过期
  20. centos配置ssh免密码登录后,仍提示输入密码

热门文章

  1. jquery-ajax基础-XMLHttpRequest
  2. Xshell 访问虚拟机中linux
  3. [SQL]存储过程建表
  4. [ASP.NET]EF跨项目调用问题
  5. javascript操作window对象
  6. “System.IO.FileNotFoundException”类型的未经处理的异常在 mscorlib.dll 中发生
  7. CDH使用秘籍(一):Cloudera Manager和Managed Service的数据库
  8. UESTC--1264--人民币的构造(数学规律)
  9. 敏捷开发 —— TDD(测试驱动开发)
  10. Redis学习笔记(十一) 命令进阶:Connection(连接)