前言想象我在口胡三样我都不熟悉的东西并尝试称之为“学习笔记”。其实不过是我自己对于它的一点小理解，甚至可能是错误的！无所谓，口胡！口胡！口胡！口胡！口胡！一些备注\(dfn_u\)为点\(u\)的dfn序，\(nfd_i\)表示第\(i\)个dfs到的点是啥（前者的反数组）dfs序求lca这个很简单，想

虚树给定一棵树，树上有一些关键点，你要建另一棵树，保留关键点，以及任意一对关键点的\(\text{LCA}\)。当你发现对于一棵树，你只有一些关键点有用的时候，就可以尝试建虚树。两次排序思路先把所有点按\(\text{dfn}\)序排序，然后把\(\text{dfn}\)相邻的两个点取出来，再把它们的\(\t

虚树什么是虚树虚树常常被用在树形\(dp\)中。当一次询问仅仅涉及到整棵树中少量节点时为每次询问都对整棵树进行\(dp\)在时间上是不可接受的。此时，我们建立一棵仅仅包含部分关键节点的虚树，将非关键节点构成的链简化成边或是剪去，在虚树上进行\(dp\)。虚树包含所有的询问点及它们

虚树简介虚树一般用于树形DP中，可以有效减少冗余的计算量。其原理是将对DP无影响，或者在影响可快速运算范围内的点缩在一起，从而使得整棵树大小极大的减小。因此，可以使用虚树的题目一般有特殊点之类的设定，多测并限定特殊点的总量。P2495[SDOI2011]消耗战一道经典的虚

对dfn序开数据结构（如线段树），每个结点\(p\)维护对应dfn序区间内所有存在的点所构成的虚树大小\(sz_p\)，需要维护区间内所有存在的点中dfn序最大点\(rv_p\)和最小点\(lv_p\)、区间内所有存在点的LCA\(lca_p\).考虑合并左右儿子\(ls,rs\)，按两棵虚树是否相交分讨，先考虑

基环树那块闲了再写。本文针对虚树板题作原理解释和介绍写法。消耗战如果不考虑多测那么这是一道裸的树形dp。令\(dp_u\)表示切断以\(u\)为根的子树里所有关键点的最小花费。\[ans=dp_{root}=dp_1\]\[dp_u=min(minv_u,\sum_{v\inson_u}dp_v)\]其中\(minv_u\)表示切

1引入首先看这样一道题：[SDOI2011]消耗战有一棵树，边上有边权。每次询问给出\(k\)个点，找到一些边，使得删去这些边后从\(1\)号节点无法达到这\(k\)个点中任意一个，同时使边权最小。显然这是一道树形dp。如果说只给我们一次询问，可以很简单的\(O(n)\)求出。但是现在有了

概念什么是虚树？通俗的来说，虚树是原树的一些点集组成的树，这些点是一些关键点。在树形dp遍历中，如果每次都遍历整棵树会很浪费时间，这时候虚树就派上用场了。简介虚树的节点有哪些？在dp中，我们建立虚树包含着关键节点和关键节点的任意二者的\(\text{lca}\)。到这里，你已经会

关于虚树对于一些在树上进行某些询问的查询，且每个询问实际用到的点并不多的时候，可以考虑建虚树来查询。虚树的建立复杂度是\(O(m\logn)\)的，\(m\)是虚树节点数量，\(n\)是原树节点数量。也有方法可以做到\(O(m\logm)\)。例题题目链接。分析注意到范围：\(\sumk_i\le5

1.简介虚树，顾名思义1，就是不真实的树，常用于动态规划，所以可以说，虚树就是为了解决一类动态规划问题而诞生的当一次询问中仅涉及一颗树中的少量节点时，在整棵树上dp时间复杂度显然难以接受所以可以建立一颗只包含关键节点的树，将非关键的链简化或省略，在新树上进行dp一颗虚树包含所

虚树用途一棵树上进行m次不同的操作，每次用到k个节点（$\sumk$$O(n)级别$）用于于树上DP原理将原树里的一部分用到的节点抠出来，建一棵新树（虚树），在上面进行DP优点：降低每次操作的复杂度构建将要用到的节点（设为s）按照dfn序排序dfn序相近的在原树上

虚树学习笔记定义虚树指的是不同于原树（我称之为实树）的重构树，使得在同样能够求解的情况下，整棵树的节点数更少，从而使得在存在多次询问时，一些复杂度关于树的节点数的树上算法能够在时限内求解。常用场景一般来说，虚树的使用场景比较单一，常见于在实树上存在一些特殊节点，并且答案与

传送门给出\(n\le2\cdot10^5\)的一棵树，每个节点有一个颜色。求出路径长度为\(2\)路径首端和尾端拥有相同颜色，且路径上其他点不存在相同颜色的点的路径条数。当时看错题了，把颜色抽出来后没法做了。后来感觉能点分治，然后把题看对了，遂写了一个极其抽象的点分治。除此之外，把某

P4606[SDOI2018]战略游戏一个感觉比较新颖的题目，搞了一周题目大意：给定一个图，q组询问，每组给定k个点，求图上有几个点，删去后能使这k个点不连通题解：首先考虑删掉的点一定为割点，然后本题极像虚树，就可以考虑建圆方树然后，圆方树上的圆点，在两点路径上的，即为所求于是乎把k个点拎出来

题目只出现了一些关键点，所以想到虚树，我们对关键点建立虚树，会发现对虚树上的一条边\((u,v)\)，在原图中\(u\)到\(v\)的路径只用最多选择一条就可以了，所以我们就发现，有效的边的个数就是虚树上的边，是\(O(k)\)的然后看一下\(k\)的范围，想到状态压缩，对每一个状态\(S\)，枚举虚树中的每一条

懒得写代码了1.http://oi.nks.edu.cn/zh/Problem/Details?cid=2719&tid=F 首先有个单次询问O（n）的换根DP做法。像这种每次找一类点计算答案的题，考虑虚树。有个结论：相遇点选在颜色为x或y的点上不会更劣所以只需要在同时包含x和y色的虚树上换根DP就行了但复杂度波动不定。当ma

虚树主要是针对这一类问题：答案只跟选定的某些点（及它们的lca）有关，且选定点的总量可以接受而每次询问都搜索一遍整棵树很浪费因此建出虚树，在虚树上进行各种操作构建有两种方法：二次排序求lca，单调栈单调栈单调栈上维护的是虚树的一条链第一步肯定是将点按照dfn序排序为了

虚树学习笔记虚树，顾名思义，不是真实的树。在关于树的问题中，虚树起到缩小题目规模，优化算法的作用。算法思路引入P2495SDOI2011消耗战设\(dp[i]\)为\(i\)与所有该子树内资源丰富节点不联通的代价。如果\(u\)的儿子\(v\)，不是资源丰富节点。\[dp[u]+=\min(w(u,v),dp[

一种很有用的东西。体现了关键点的思想。应用1树上每个节点有颜色，问一个子树内有几种颜色。对每种颜色的点集按DFS序排序，点所在位置权值+1，相邻两个的LCA处权值-1。子树求和即可。正经的应用建虚树：q[hh=0]=1;for(i){ intl=lca(a[i],q[hh]); while(hh&&dep[q[hh]]>d

感觉题解做法都好神秘。来一个容易理解，通俗易懂的树剖解法。思路容易发现原问题等价于维护一个虚树。每一次询问虚树的根的所有儿子的最大值。要求链修。容易发现仅仅动态维护根是好做的。我们用一个\(\text{set}\)。每次维护\(\text{dfs}\)的最小值和最大值。对于这

虚树虚树可以应用于树形\(DP\)的加速。当题目规定查询点集的大小和\(\le10^5\)时可以用虚树解决。虚树的原理是在原树上重新建一棵树，使得树上只包含要询问的点和它们的\(lca\)。普通树形\(DP\)的时间复杂度为\(O(n^2)\)。最坏形成一棵二叉树，点集大小为\(n\)，总点数为

tarjan算法虚树DAG剖分矩阵树定理最小树形图（）斯坦纳树（感觉可以看看？）同余最短路平面图and对偶图线性规划网络流一般图最大匹配Prüfer序列竞赛图稳定婚姻问题2-sat仙人掌Dilworth定理（）tarjan算法有向图\(\to\)强连通分量无向图\(\to\)广义圆方树

虚树+DP+树剖+二维数点题意：给一棵树，每个点有一个颜色，多次查询给定\(x,d\),询问树上距离某个点\(x\)小于等于\(d\)的所有点的颜色个数，这些点显然形成一个连通块。先将询问离线，考虑对于每个点，求出每个颜色对这个点的最小距离，考虑二维数点，来计算出\(\led\)的颜色的数

2023/10/6发现找不到题做了，决定学习新算法。经过在一些题单中的翻找，决定学习虚树。Part1.引入以一道例题来引入虚树吧。[HEOI2014]大工程给定一棵有\(n\)个点的树，边权均为\(1\)。现在有\(q\)次询问。每次询问取\(k\)个点出来建立完全图。定义连接两个点的代价为

询问实际上是求笛卡尔树上的叶子结点个数，因为非叶子一定无法与子树内通信发现如果两个叶子\(u,v\)以\(\text{LCA(u,v)}\)的某一祖先\(p\)进行通信，那么\(p\)的祖先也一定能通信，保证两两能通信的关键就是一棵对于所有关键点的虚树，由于关键点之间并不存在祖先后代关系，因此笛