首页 > 其他分享 >虚树

虚树

时间:2024-02-14 22:12:34浏览次数:156  
标签:int top stk dfn lca 虚树

虚树

主要是针对这一类问题:答案只跟选定的某些点(及它们的 lca)有关,且选定点的总量可以接受

而每次询问都搜索一遍整棵树很浪费

因此建出虚树,在虚树上进行各种操作

构建

有两种方法:二次排序求 lca,单调栈

单调栈

单调栈上维护的是虚树的一条链

第一步肯定是将点按照 dfn 序排序

为了方便,先把根加入栈

加入点 \(x\) 时,先求出它和栈顶的最近公共祖先 \(lca\)

  • 如果 \(lca\) 就是栈顶,那么 \(x\) 依然在这条链上,直接将 \(x\) 入栈,跳过
  • 否则说明 \(x\) 在另外一条链上,先把栈中边的更高点 dfn 序都比 \(lca\) 大的边的下端点弹出并连这条边,被弹出的点不可能在新的链上
  • 然后判定栈顶是否为 \(lca\)
    • 如果栈顶是 \(lca\),那么说明 \(lca\) 已经入栈,跳过
    • 否则 \(lca\) 一定是栈顶元素的祖先,连上 \(lca\) 与栈顶的边,弹出栈顶并加入 \(lca\)
  • 最后将 \(x\) 入栈

不要忘记完成后栈内元素之间没有连边

但是我们在这个过程中默认了根在虚树中,很多情况下是没有问题的,如果题目要求比较特殊,根不能额外添加到虚树中,则插入时特判,如果根在点集中或者根在栈内元素连边之前已经有边,那么根本来就在虚树中,否则栈内元素连边时要跳过根

注意边的清空

void add(int u, int v)	{edge[u].pb(v);}
void build(vector<int> p)
{
	top = 0, stk[++top] = 1;
	sort(p.begin(), p.end(), [](const int x, const int y){return dfn[x] < dfn[y];});
	int flag = 0;
	for(int x : p)
	{
		if(x == 1)	{flag = 1;	continue;}
		int lca = getlca(stk[top], x);	del.pb(lca); 
		while(top > 1 && dfn[stk[top - 1]] > dfn[lca])	add(stk[top - 1], stk[top]), --top;
		if(dfn[lca] < dfn[stk[top]])	add(lca, stk[top]), --top; // 这里的 < 相当于 !=
		if(!top || lca != stk[top])	stk[++top] = lca;
		stk[++top] = x;
	}
	root = (!flag && !edge[1].size()) ? stk[2] : stk[1]; // 特判 1
	for(int i = (!flag && !edge[1].size()) ? 3 : 2; i <= top; ++i)	add(stk[i - 1], stk[i]);
}

二次排序

二次排序方法思路更简单,按 dfn 序排序后再对相邻元素求 lca,把得到的所有点再排序去重

然后就没了

比较

虽然不得不说二次排序思路简单,不容易写错

但个人还是比较喜欢用单调栈,因为我觉得单调栈这种动态加入构建的方式更有扩展性,常数较小,而且合并时由于 dfn 序已经有序,可以做到线性合并两个点集虚树

但每次动态加入一个点则需要二次排序的思路,插入 dfn 序对应位置后求与相邻两个数的 lca 并加入

性质

首先,虚树的大小为 \(O(|S|)\),这是构建方法和复杂度有保障的前提

如果将虚树上每个点到虚树的根的路径上所有点都加入虚树,那么,子节点数量 \(\ge 2\) 的点个数也只有 \(O(|S|)\)

虚树边权和为所有时间戳循环相邻的点距离之和除以 \(2\)

每条边会被正反经过各 \(1\) 次

虚树差分:如果把虚树上所有点到根路径上的点权值 \(+x\),则把关键点本身 \(+x\),dfn 序排序后相邻点的 \(lca\) 处 \(-x\),做树上前缀和(求子树内权值和)即可

同二次排序的过程

正权虚树的封闭性:

类比正权直径的封闭性,两个点集的直径可以合并得到新点集的直径

这里同理,定义点集前 \(k\) 大虚树为点集中选取 \(k\) 个点,使形成虚树的边权总和最大(当 \(k=2\) 时退化为直径)

那么两个点集的前 \(k\) 大虚树可以合并,先对点集中所有点建虚树,然后再上面用长链剖分的技巧,以直径端点为根,贪心选前 \(k-1\) 大长链,选出的叶子节点就是合并后虚树的关键点

20231008 模拟赛订正

应用

优化 DP

P2495 [SDOI2011] 消耗战

CF613D Kingdom and its Cities

标签:int,top,stk,dfn,lca,虚树
From: https://www.cnblogs.com/KellyWLJ/p/18015676

相关文章

  • 虚树学习笔记
    虚树学习笔记虚树,顾名思义,不是真实的树。在关于树的问题中,虚树起到缩小题目规模,优化算法的作用。算法思路引入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......
  • [学习笔记]虚树
    虚树虚树可以应用于树形\(DP\)的加速。当题目规定查询点集的大小和\(\le10^5\)时可以用虚树解决。虚树的原理是在原树上重新建一棵树,使得树上只包含要询问的点和它们的\(lca\)。普通树形\(DP\)的时间复杂度为\(O(n^2)\)。最坏形成一棵二叉树,点集大小为\(n\),总点数为......
  • 虚树 学习笔记
    2023/10/6发现找不到题做了,决定学习新算法。经过在一些题单中的翻找,决定学习虚树。Part1.引入以一道例题来引入虚树吧。[HEOI2014]大工程给定一棵有\(n\)个点的树,边权均为\(1\)。现在有\(q\)次询问。每次询问取\(k\)个点出来建立完全图。定义连接两个点的代价为......
  • 【线段树合并、虚树】P5327 [ZJOI2019] 语言
    终于1kAC了家人,感动吧。贺了很久,很累。前置题目:P3320[SDOI2015]寻宝游戏虚树的边权和:\[\sumdep_{a_x}-\sum_{x<n}dep_{a_x,a_{x+1}}-dep_{a_{1},a_{n}}\]考虑转化贡献,求过该点的链的并,最后再除以二即可。那么我们可以考虑维护以该点的子树的所有关键点以及......
  • 【学习笔记】虚树
    点击查看目录目录定义构造虚树二次排序+LCA连边单调栈虚树,不是虚数\(i\)。定义在树形dp等题目中,树中点很少,可以直接跑dp。但是如果很大但是我们只需要查询很少的一些点呢?我们称某次询问的点为【关键点】。我们看上图,只有左边子树的两个节点被查询了,那右边的子树有......
  • 【学习笔记】(24) 虚树
    虚树常常被使用在树形dp中,当一次询问仅仅涉及到整颗树中少量结点时,为每次询问都对整棵树进行dp在时间上是不可接受的。此时,我们建立一颗仅仅包含部分关键结点的虚树,将非关键点构成的链简化成边或是剪去,在虚树上进行dp。虚树包含所有的询问点及它们之间的lca。显然虚树的叶子节点......
  • 虚树学习笔记
    观前须知:本博客中\(k\)均指关键点数量-2前置芝士你需要会基本的dfs序(下简称dfn)及性质,并且要会写LCA(推荐树剖因为快)-1典型特征关键点\(\sumk\le1e5\)之类的很小的数虚树的特点是只保存关键点及其LCA0引入例:\(\color{green}CF613D\)这个树上问题可以说非常......
  • 浅谈虚树优化线段树
    前言我们都知道动态开点权值线段树的空间复杂度是\(O(n\logV)\)的,但是很多题目中这样的空间是会被卡的,那我们能不能优化呢?实现看看下面这一棵树:在上图中,红色节点使我们平常会开的点。但是我们发现,其实只要维护绿色的点和红色的叶子结点。其实,绿色节点就是所有叶子结点......
  • 虚树 学习笔记
    模板题题目传送门给定一棵树,每次给出\(k\)个点,断掉一些边,然后让这些给出的点和\(1\)号点不连通,求断边的边权和的最小值。数据组数\(T\le5\cdot10^5\),树的点数\(n\le2.5\cdot10^5\),\(\sumk\le5\cdot10^5\)题目解析我们发现每次给出的是一部分点,所以我们只需要......