【BZOJ】2060: [Usaco2010 Nov]Visiting Cows 拜访奶牛
2024-10-22 08:41:30
【算法】树形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 ;
}
最新文章
- Maven+Spring Profile实现生产环境和开发环境的切换
- 【结果很简单,过程很艰辛】记阿里云Ons消息队列服务.NET接口填坑过程
- CodeForces 670D2 Magic Powder 二分
- ECSTORE AJAX提交的实现
- 依赖注入(DI)和控制反转(IOC)
- myeclipse如何恢复已删除的文件和代码
- UVA 624 CD (01背包)
- 获取sd卡的总大小和可用大小
- 关于margin-top的一些特别问题
- C++关联容器知识总结
- ns3构建2 core fat tree出错
- Scrapy突破反爬虫的限制
- python 类的介绍实例
- IDEA拷贝操作
- Python中read()、readline()和readlines()三者间的区别和用法
- [Sphinx]全文索引Sphinx的使用配置
- 简单复利计算c语言实现
- ES6简单总结
- [转]如何在Windows Server 2012中安装.Net Framework 3.5?
- 富文本编辑器 summernote.js