bzoj 2060: [Usaco2010 Nov]Visiting Cows 拜访奶牛【树形dp】
2024-08-31 17:46:21
设f[u][0/1]为u这个点不选/选,转移的时候从儿子转移,f[u][1]=sum(f[son][0])+1,f[u][0]=sum(max(f[son][0],f[e[i].to][1]))
#include<iostream>
#include<cstdio>
using namespace std;
const int N=50005;
int n,h[N],cnt,f[N][2];
struct qwe
{
int ne,to;
}e[N<<1];
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
void add(int u,int v)
{
cnt++;
e[cnt].ne=h[u];
e[cnt].to=v;
h[u]=cnt;
}
void dfs(int u,int fa)
{
int s0=0,s1=0;
for(int i=h[u];i;i=e[i].ne)
if(e[i].to!=fa)
{
dfs(e[i].to,u);
s0+=f[e[i].to][0];
s1+=max(f[e[i].to][0],f[e[i].to][1]);
}
f[u][0]=s1;
f[u][1]=s0+1;
}
int main()
{
n=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y),add(y,x);
}
dfs(1,0);
printf("%d\n",max(f[1][0],f[1][1]));
return 0;
}
最新文章
- Java MD5加密工具类
- SQLServerDBA十大必备工具---让生活轻松点(转)
- uniPanel特效
- Static File Middleware
- nginx -t ";nginx: [warn] only the last index in ";index"; directive should be absolute in 6 ";的问题解决
- poj1185:炮兵阵地(状压dp)
- Java数据结构习题_算法分析
- [JSOI2009]游戏Game
- pandas 必背函数操作
- iP私网地址
- shiro与项目集成开发
- Android并发编程 开篇
- Codeforce Div-2 985 C. Liebig&#39;s Barrels
- Python内置类型——list
- parent获取子元素以及自身元素
- 【图像处理】openCV光流法追踪运动物体
- HDU 3068 最长回文 manacher 算法,基本上是O(n)复杂度
- (博弈)Simple Game --codeforces--570B
- Go基础---->;go的基础学习(一)
- Linq中连接
热门文章
- python之字符串处理 2014-4-5
- C++——";%";运算符
- 【状压+状态转移】A Famous Airport Managere
- [K/3Cloud] 创建一个操作校验器
- list去重精简代码版
- URL传递多个参数遇到的bug
- Redux 中文文档
- [TypeScript] Use TypeScript’s never Type for Exhaustiveness Checking
- VBS 操作Word
- Java学习笔记----你可能不知道那些知识,对象复制与引用