【树形DP】BZOJ 1131 Sta
2024-09-06 18:37:45
题目内容
给出一个\(N\)个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大
输入格式
给出一个数字\(N\),代表有\(N\)个点。\(N \le 1000000\)。下面\(N-1\)条边。
输出格式
输出你所找到的点,如果具有多个解,请输出编号最小的那个。
样例输入
8
1 4
5 6
4 5
6 7
6 8
2 4
3 4
样例输出
7
思路
看到\(N \le 1000000\),只能是用\(O(N)\)的效率了。
假设当前得到的答案在结点u,要把答案转移到子结点v。
这样就会有\(n-size[v]\)的节点深度+1,\(size[v]\)的节点深度-1。
变化就是\(n-2size[v]\)的深度和。
从上向下dp。
最新文章
- Linux如何下解压windows下的.zip和.rar文件
- 【实践】jquery实现滑动动画及轮播
- LeetCode----8. String to Integer (atoi)(Java)
- Android Studio使用中的异常
- Iframe刷新父窗口的几种方式
- NPM使用
- Android Material Design的FloatingActionButton,Snackbar和CoordinatorLayout
- 蜂鸟A20开发板刷 cubietruck 的 SD 卡固件
- Linux下使用ps命令来查看Oracle相关的进程
- Oracle本地管理对照数据字典管理表空间
- H5仿微信界面教程(一)
- 用python批量修改文件名
- Mac下redis的安装 以及配置支持PHP使用redis
- git杂记:忽略ssl认证
- 客户端负载均衡Feign之三:Feign补充
- 服务器使用VMware系软件管理主机集群
- tensorflow 在同一个GPU同时加载多张相同的图
- 监测uitableview 向上滑动和向下滑动的事件
- tp3.2 ajax 表单提交
- python 发qq邮件
热门文章
- Unity接入多个SDK的通用接口开发与资源管理(一)
- [程序员代码面试指南]栈和队列-最大值减去最小值 小于或等于num 的子数组的数量(单调队列)
- SSM框架中,事务无法回滚的原因和解决
- spring mvc(2) spring mvc初体验
- 4.案例 - NIO实现TCP通信
- .netcore+vue 实现压缩文件下载
- linux学习(一)认识阿里云
- LeetCode刷题总结-动态规划篇
- JS寄快递地址智能解析
- 038 01 Android 零基础入门 01 Java基础语法 04 Java流程控制之选择结构 05 案例演示switch结构-星期的表示案例以及总结