之前说过这题能用点分治（详见 http://www.cnblogs.com/jasonyu/p/noi2014.html），但其实还有更粗暴的解法。

要求出一个点的答案，我们需要知道树上一段路径的点形成的下凸壳。不过我们其实也不一定非要知道这整段的下凸壳，分成合适的段数分别二分求最优值也可以。假如是一条链的话，用线段树就可以了。对于树，我们就再套一层树链剖分。下面说一下具体做法。

首先树链剖分一下。然后考虑在树的dfs序（或bfs序）中，排在前面的点的答案不会依赖于后面的点的答案，所以我们可以按照dfs序（或bfs序）来计算答案，然后将当前点插入。由于每条链上的点都是按照深度从小到大加入的，所以新点只会在凸壳尾部，不用套平衡树，直接开vector就行了。由于每个点只影响在logn个线段树节点，所以空间复杂度为O(nlogn)；树链剖分后每条路径经过重链数为O(logn)，对每条重链上的一段线段树可将其分为O(logn)段，每段找最优值复杂度为O(logn)，所以保守地分析得O(n(logn)^3)是其复杂度上界。但是感觉其常数至少应该是很小的。

最新文章

1. Asp.net中存储过程拖拽至dbml文件中，提示无法获得返回值
2. java面向对象三大特性之继承
3. 用Join子句进行分组联接
4. GET请求参数为中文时乱码分析
5. python 练习 5
6. Java——正则表达式（字符串操作）
7. themeforest 模板
8. 历代诗词咏宁夏注释3----蔡升元:<题大清渠>
9. 终端I/O之获得和设置终端属性
10. （转）CentOS5.5 下搭建 PHP 环境（最佳的LAMP环境）
11. 在C#中实现Socket端口复用
12. segv & mini coredump
13. ID3决策树预测的java实现
14. Java原子变量
15. java中一个引人深思的匿名内部类
16. 【原】Oracle EBS 11无法打开Form及Form显示乱码的解决
17. 老王带你走过 Kafka 入门教程
18. Web API中使用CORS解决跨域
19. jvm--深入理解java虚拟机 精华总结（面试）（转）
20. QtCreator添加第三方头文件和类库

热门文章

1. 二维码_encode与decode
2. mysql 查询某字段里含有(或者不含)某字符的所有记录方法(转)
3. 【网络流#2】hdu 1533 - 最小费用最大流模板题
4. Windows Native API
5. OD: SEHOP
6. z-index优先级总结
7. php的一些基本概念梳理
8. Phonegap 版本minSdkVersion为8的时候的自动更新与升级
9. (转)xml节点和元素的关系 .
10. 【转】深入理解Java内存模型（七）——总结