【算法】树形DP

【题解】没有上司的舞会?233

f[x][0]=∑max(f[v][0],f[v][1])

f[x][1]=(∑f[v][0])+1

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=; struct edge{int v,from;}e[maxn*];
int first[maxn],n,f[maxn][],tot=; void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
void dfs(int x,int fa){
f[x][]=;f[x][]=;
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){
dfs(e[i].v,x);
f[x][]+=max(f[e[i].v][],f[e[i].v][]);
f[x][]+=f[e[i].v][];
}
}
int main(){
scanf("%d",&n);
int u,v;
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
insert(u,v);insert(v,u);
}
dfs(,);
printf("%d",max(f[][],f[][]));
return ;
}

最新文章

  1. Maven+Spring Profile实现生产环境和开发环境的切换
  2. 【结果很简单,过程很艰辛】记阿里云Ons消息队列服务.NET接口填坑过程
  3. CodeForces 670D2 Magic Powder 二分
  4. ECSTORE AJAX提交的实现
  5. 依赖注入(DI)和控制反转(IOC)
  6. myeclipse如何恢复已删除的文件和代码
  7. UVA 624 CD (01背包)
  8. 获取sd卡的总大小和可用大小
  9. 关于margin-top的一些特别问题
  10. C++关联容器知识总结
  11. ns3构建2 core fat tree出错
  12. Scrapy突破反爬虫的限制
  13. python 类的介绍实例
  14. IDEA拷贝操作
  15. Python中read()、readline()和readlines()三者间的区别和用法
  16. [Sphinx]全文索引Sphinx的使用配置
  17. 简单复利计算c语言实现
  18. ES6简单总结
  19. [转]如何在Windows Server 2012中安装.Net Framework 3.5?
  20. 富文本编辑器 summernote.js

热门文章

  1. laravel开发环境部署遇到的问题和个人感受
  2. 对编码内容多次UrlDecode
  3. eg_4
  4. OSPF学习中的问题
  5. TCP系列09—连接管理—8、TCP Reset
  6. 3dContactPointAnnotationTool开发日志(十五)
  7. ZOJ 2072 K-Recursive Survival
  8. 微信小程序wx.pageScrollTo的替代方案
  9. MyBatis配置和日志
  10. 【Python】PYTHON 函数局部变量和全局变量