夜间模式暗黑模式
字体
阴影
滤镜
圆角
虚树

其实虚树这一套没什么,就是一个板子。主要解决的是给一个树,然后对树上的某个点集搞些什么操作啊询问啊,之类的问题。

就是把原树的dfs序搞出来,然后把要搞的点和lca拿出来,搞一棵新的树,用单调栈来时限,其实就是一个模板。

例题是bzoj 3611

给定一棵树,然后询问一个点集的所有互相之间的路径和以及最长路径最短路径

把虚树建出来,然后就树dp随便维护最长链最短链就好了,很显然。

暂无评论

发送评论


				
上一篇
下一篇