首页 > 其他 > 详细

[学习笔记]虚树

时间:2019-02-13 22:33:10      阅读:184      评论:0      收藏:0      [点我收藏+]

前言&&思想

一些给定树上一些点集,要处理和该点集有关的询问(例如和点集关系,点集选择限制)的题目,

很多子树没有变化,暴力没有意义。

提取出有关的点和路径,构成虚树

虚树上DP等等,难点往往在于找到非虚树部分的答案。

 

建立

1.暴力sort再sort

2.LCT,还支持换根

 

例题

消耗战

 

世界树

 

 

结合

动态DP

整体DP

 

[学习笔记]虚树

原文:https://www.cnblogs.com/Miracevin/p/10372049.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!