虚树大意：通过建一棵只包含询问点和不超过询问点数减一个lca的树来减少点的个数，降低时间复杂度 这东西不难，常用于辅助树形dp，难点在于dp… 使用该算法的标志为不确定组的询问次数与给出的询问点数和 例如： 每次询问w个数， ∑ i = 1 q w i = 300000 \sum_{i=1}^qw_i=300000\quad ∑i=1q​wi​=300000 算法： 构建过程十分简单，放

题目大意： 给定一棵根节点为1的带边权的树。 每次给定一些点，求把这些点与树根断开的最小花费。 题目分析： 我们可以O（n）处理出每个点与根断开的最小花费，即该节点到根的路径上的最小边权。 然后我们对于每一个询问，可以把询问的点打上标记，然后可以O（n）动态规划求解。 但是O（n）的时间复杂度接受不了，而且我们发现每次询问并不会询问所有的点，而且询问的总点数不超过50w。 这样我们可

虚树入门 题目传送门 虚树的主要思想就是对于一棵树，仅仅保留有用的点，重新构建一棵树。 #include<bits/stdc++.h>#define il inline#define pb push_back#define ms(_data,v) memset(_data,v,sizeof(_data))#define SZ(a) int((a).size())using name

Description 在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望

问题引入: m个询问, 每次给出k个点, 求使这k个点都不与根连通的最小代价 ( m <= 250000, sum(k) <= 500000)   虚树: 类似有很多组询问, 而询问总点数又较小的, 可以用虚树解决, 具体来说, 就是将每次的k个点重新建一棵树, 然后在这颗树上DP   建树的方法 : 总体来说, 就是用栈维护一个根到当前点的链, 栈中的节点就是根到栈顶路上的所有关键点,

世界树 金牌导航 虚树-1 luogu 3233 题目大意 对于一棵树，给出若干询问，每个询问告诉你若干个特殊点，对于所有点，都会选择离自己最近（距离相等就选编号最小的）的特殊点，问对于所有特殊点，有多少个点选择该点 输入样例 10 2 1 3 2 4 3 5 4 6 1 7 3 8 3 9 4 10 1 5 2 6 1 5 2 7 3 6 9 1

传送门 虚树毒瘤题 首先注意到 m m m只比 n n n大 10 10 10，所以可以随便找个生成树，把 m m m多出来的边上的点都拎出来建一个虚树，可以枚举每条边的深度较浅的那个点选不选，在虚树上树形 d p dp dp，然后发现虚树上父亲到儿子的系数是不变的，所以可以树形 d p dp dp预处理出来 k [ u ] [ 0 / 1 ] [ 0 / 1 ] k[u][0/1][0/

传送门 这题调的我两眼发黑。。。 首先想 S A M SAM SAM建出来就是反串的后缀树，那么把原串反转一下，求后缀的 l c p lcp lcp就变成了求前缀的最长后缀，在 S A M SAM SAM上就是两个代表节点 l c a lca lca的 l e n len len，用这些关键点和他们的 l c a lca lca建出虚树，然后在虚树上跑，设 s i z a [ u ] , s

这玩意好难啊Orz 完全不理解那个模拟深搜到底是什么鬼 果然像我这样的人最好早点滚粗  要简历虚树 首先要选出虚树里面的点 那么关键点和关键点的LCA都要加入到虚树中来 那我们就深搜一遍 处理出每个节点的dfn值和儿子数  按照dfn值依次枚举每一个关键节点 这样可以把同一棵子树内的节点一起找到 用一个深度单调的栈来维护树中的节点 每次取出一个关键点 求出它和栈顶元素的lca  如果

Description (我并不想告诉你题目名字是什么鬼) 有一个长度为n的仅包含小写字母的字符串S,下标范围为[1,n]. 现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在S中出现的起始位置来表示),求这些后缀两两之间的LCP(LongestCommonPrefix)的长度之和.一对后缀之间的LCP长度仅统计一遍. Input 第一行两个正整数n,m,分别表示S的长度以