这是个用来处理树上问题的东西，一般题目的形式都是 如果发现，对于每组点，在树上做决策时只需要关心 而虚树这个东西，是只包含 其实过程说白了也很简单，就是将需要的点拿出来重新建一棵树而已。 具体来说，我们需要预处理出原树上每个点的 在插入时，我们需要维护一个栈 然后分类讨论一下： 因为是按 然后要注意的是弹栈时要把边连上，以及一丢丢需要连边的细节就看代码吧： [SDOI2011]消耗战 题解
介绍
给出一棵树，多组询问这样子，然后每次询问会给你一些点，询问的问题一般只关心这些点。这些点以及这些点的lca们，那么就可以考虑建出他们的虚树，然后在虚树上进行下一步操作。这些点以及这些点的lca们的，而这些点的lca们与这些点的数量级是相当的，所以建树的时间复杂度基本上就是
，其中
等于所有询问给出的总点数，乘上
是因为需要求
。建树过程
序，然后每次询问时将每个点按照
序从小到大依次插入进新树。
，记录从根节点到上一次插入的元素
之间的路径，然后对于新插入的元素
，先求出它和
的
，记为
。
在
的子树内，那么直接插入到栈顶即可
和
放入栈中
序插入的，所以假如
不在
的子树内，那么说明
的子树内的关键点都处理完了，直接弹掉是没问题的。//一开始栈中只有一个元素，即树根 int zhan[maxn],t; void add(int x) { if(t==1)return (void)(zhan[++t]=x); int lca=get_lca(zhan[t],x);if(lca==zhan[t])return (void)(zhan[++t]=x);//x在栈顶元素的子树中 while(deep[zhan[t-1]]>=deep[lca])buildroad(zhan[t-1],zhan[t]),t--;//否则弹栈+连边 if(zhan[t]!=lca)buildroad(lca,zhan[t]),zhan[t]=lca; zhan[++t]=x;//将lca和x插入 } 题表
可能还会更新？
CF613D Kingdom and its Cities 题解
[HNOI2014]世界树 题解
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
