Tag-虚树

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2020-07-12 22:40:20 |  0 Comments  |  DP 虚树

Luogu P2495 [SDOI2011]消耗战 虚树+树形DP

 

题解

本人的虚树入门题。

基础思想

题目意思相当于m次询问,每次询问给出一些点,要我们付出一定代价断边使得给出的这些点与根节点1不连通.

首先肯定能确定这个题是一个树形DP。转移方程也非常好写。

考虑对于单次询问,我们设f[x]为处理完以x为子树的最小的代价。

那么转移无非是两种情况:

1.断开与父亲的连接,代价为从x到根1的路径上的最小值。

2.当该点不是询问点的时候,把子树内所有询问点都与根节点断开的代价。

但是这样有一个问题,每次询问都是O(n)的,来看一下数据范围:

很明显O(nm)的做法是无法处理的。

进阶优化 & 虚树的引出

但实际上,我们在对每一次询问的处理中,考虑了很多无用点的信息。

考虑一下,很容易能够明白,实际上,只有询问点、其LCA、其LCA的LCA及其三次LCA……等,对这些点和上面的根进行断开是实际在最小答案中有效的,处理其他的点实际上无效。

所以虚树就应运而生了。

虚树是主要运用在树形DP中的一类构造方法,旨在只将对答案有用的点拿出来构造一棵虚拟的新的树,以此来降低算法的复杂度。

举个栗子,在本题的样例中有这样的数据。

对于样例中的询问数据

3
2 10 6
4 5 7 8 3
3 9 4 6

其对应的虚树分别是以下的形式

第二个询问中,由于点7、8均在5的子树内,故断开5以及根节点的连接即可,7、8实际上是无用点(仅对此题而言,不同题目要考虑不同的构造)

虚树的构建

现在需要考虑的是如何构建虚树。

首先我们要先对整棵树dfs一遍,求出他们的dfs序,然后对每个节点以dfs序为关键字从小到大排序(本人比较喜欢用树链剖分里面的那种形式)

同时维护一个栈,表示从根到栈顶元素这条链

假设当前要加入的节点为pp,栈顶元素为x=s[top]x=s[top]lcalca为他们的最近公共祖先

因为我们是按照dfs序遍历,因此lcalca不可能是pp

那么现在会有两种情况

  1. lcalcaxx,直接将
Title - Artist
0:00