之前写在洛谷,结果没保存,作废……

听说考前写题解RP++哦

思路

很容易想到是

树形DP

如果树形DP不知道是什么的话推荐百度一下

我在这里用vector储存边

设状态f[i][0]为i点不访问,f[i][1]为i点访问

那么f[u][1] +=  f[y][0]表示u点要访问,(u,y)有连边
f[u][0] +=  max(f[v][0], f[v][1])表示u点不访问,(u,y)有连边

上面就是我们的转移方程了

介绍一下vector吧

vector是STL里的一个向量容器

也叫动态数组

就是不定长的数组

用来储存边非常好用

因此我在这里用vector给大家演示一下

代码

 #include<bits/stdc++.h>//万能头
#define ll long long//作废
using namespace std;//标准头
#define N 50005
int f[N][];//DP
vector<int>son[N];//建图
bool v[N];//标记是否访问
inline int read() {
int f = , x = ; char ch;
do { ch = getchar(); if (ch == '-')f = -; } while (ch<'' || ch>'');
do { x = x * + ch - ''; ch = getchar(); } while (ch >= ''&&ch <= '');
return f * x;
}//读入优化 不解释
int dp(int u)//以u为根节点
{
f[u][] = ;//初始值1
for (int i=;i<son[u].size();i++)//用vector访问每一个点
{
int y=son[u][i];//y为下一个要搜的点 即子节点
if(!v[y]) //如果子节点没被访问
{
v[y]=true;//标记
dp(y);//递归访问
f[u][]+=max(f[y][],f[y][]); //转移方程 上面有解释
f[u][]+=f[y][];
}
}
}
int main()
{
int n=read();
for(int i=;i<n;i++)
{
int x=read(),y=read();
son[x].push_back(y);//用vector建边
son[y].push_back(x);
}
memset(v,,sizeof(v));memset(f,,sizeof(f));
v[]=true;//初始值
dp();//以1为根
printf("%d\n",max(f[][],f[][])); //输出
return ;
}

最新文章

  1. 对git的认识
  2. google.GIS小例子
  3. apache配置Allow详解及25个常见问题
  4. 腾讯云Centos下Nginx反向代理Apache+Tomcat
  5. 【整理】--【GPIO】OK6410
  6. MongoDB: CURD操作
  7. WPF中viewmodel层怎样得到view层的TabControl控件对象?
  8. vc 递归删除非空文件夹
  9. 简单登录案例(SharedPreferences存储账户信息)&amp;联网请求图片并下载到SD卡(文件外部存储)
  10. Java中两种实现多线程方式的对比分析
  11. [置顶] Asp.Net底层原理(二、写自己的Asp.Net框架)
  12. hdu1535(最短路)
  13. hadoop的安装和配置(三)完全分布式模式
  14. [LeetCode] Employee Importance 员工重要度
  15. 7.1Python异常处理
  16. Python数据类型深入学习之数字
  17. How do I update a GitHub forked repository?
  18. [笔记]python
  19. springCloud4---feign
  20. Linux下parted分区超过2TB硬盘-分区格式化

热门文章

  1. C# 不使用递归遍历目录树中的文件和文件夹
  2. StackService.Redis 应用
  3. WebApi服务以及跨域设置
  4. Exception in thread &quot;main&quot; java.lang.NullPointerException
  5. 学习笔记: 反射应用、原理,完成扩展,emit动态代码
  6. webpack项目打包配置
  7. 树递归写法ref实现
  8. git报错处理
  9. Java集合源码学习(四)HashMap
  10. JSP基础知识➣客户端请求与服务端响应(三)