换根dp:
- 第一次dfs 处理儿子点的权值
- 第二次dfs 处理 父亲点,和兄弟节点的权值
- 处理兄弟节点的时候, 利用父亲节点统一处理, 利用stl存储
斜率优化:
- 为什么会用到斜率优化: 在遇到转移式子是 fi x fj 的时候, 不是分开的, (分开的,直接用单调队列处理) (通常会遇到平方式子)
- 把i 和 j 的式子分开, 然后 抽象成x y
- 然后通过题意: 求max, 就是向上的凸包, 求min 就是向下的 凸包
- 然后要找的那个点利用二分去找就可以了, 找斜率第一个比他大..小的点就可以了
- 注意开long double
题目大意:
- 给一个树,给出树的边权, 问每一个节点的最大值
-
思路:
- 换根DP+斜率优化