首页 > 其他分享 >虚树

虚树

时间:2024-01-18 22:57:56浏览次数:35  
标签:颜色 dep sqrt hh 虚树 DP

一种很有用的东西。体现了关键点的思想。

应用1

树上每个节点有颜色,问一个子树内有几种颜色。

对每种颜色的点集按 DFS 序排序,点所在位置权值 +1,相邻两个的 LCA 处权值 -1。子树求和即可。

正经的应用

建虚树:

q[hh=0]=1;
for(i){
	int l=lca(a[i],q[hh]);
	while(hh&&dep[q[hh]]>dep[l]){
		if(dep[q[hh-1]]>dep[l]) add(q[hh-1],q[hh]);
		else add(l,q[hh]);
		--hh;
	}
	if(q[hh]!=l) q[++hh]=l;
	if(l!=a[i]) q[++hh]=a[i];
}
while(hh){
	add(q[hh-1],q[hh]);
	--hh;
}

最喜欢的一种写法,思路很清晰,特判少。

本质是堆维护当前右链。为了有一个固定的根,可以默认把 \(1\) 放进去。

注意清空虚树时要在 DFS 里面动态删。

结合树形 DP

对树上某些关键点进行修改并询问一些没有修改很好做的东西。这时候可以用虚树结合 DP 处理。

(一些简单DP题)

Plus-对树上不同类型点累计贡献(换根DP)

典型的一个题:颜色路径

如果固定了一种颜色,求别的颜色到它的距离是容易的,换根DP即可。

这道题询问了非常多次两种颜色之间所有路径的长度和。考虑分类处理。

有一个关键性质是所有颜色的点数和是 \(n\)。所以点数大于 \(\sqrt n\) 的颜色少于 \(\sqrt n\) 种,对于这部分跑虚树,复杂度 \(O(n\sqrt n)\)。

考虑小于的怎么办,一个很“启发式”的想法是对于询问的一对颜色,谁点数多就在谁的虚树上算,这样小于 \(\sqrt n\) 的东西接受的询问也是小于 \(\sqrt n\) 的一些颜色,由于总共 \(Q\) 组询问,所以这部分的复杂度总和是 \(O(Q\sqrt n)\)。

所以这道题最终的复杂度就是 \(n\sqrt n\) 级别的,由于虚树的大常,实际上比正常根号算法跑得慢了许多。

标签:颜色,dep,sqrt,hh,虚树,DP
From: https://www.cnblogs.com/mRXxy0o0/p/17973596

相关文章

  • [学习笔记]虚树
    虚树虚树可以应用于树形\(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\)题目解析我们发现每次给出的是一部分点,所以我们只需要......
  • 虚树
    我们用单调栈来建虚树,如果求lca的复杂度为\(O(\logn)\)的话,整个求虚树的复杂度应该为\(O(n\logn)\)。整体思路为我们用首先把所有关键点按照dfs序排序,然后首先把\(1\)节点加入栈。整个过程我们维护一条左链。我们考虑往里面加入一个新的关键点。求一下这个点和栈顶的......
  • 虚树 学习笔记
    虚树学习笔记引入我们在解决树上问题时,往往都是对整棵树进行处理,或者每次询问都对一个点、点对进行处理,这类题型一般都可以通过dp、树剖解决;然而,有一类问题要求我们每次对树上一些关键点进行处理。这类问题的特点就是询问次数多,而询问的点的总数不多。可如果我们每次都把整棵......