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

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

例题是bzoj 3611

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注