学习笔记——树形DP

Vemn_Noob · 2019-08-28 18:28:56 · 个人记录

树形DP的懵逼学习

现状：有点感觉

最近更新时间： 2019.09.07 12：10

树形DP题目：

1. [ 福建省历届夏令营 ] 没有上司的舞会
2. 选课
3. 战略游戏
4. [ ZJOI2008 ]骑士
5. [ USACO10MAR ] Great Cow Gather
6. [ SDOI2011 ] 消耗战

   基本模型：

   • 从根到叶节点：

     通常来说，要完成初始化/收集数据，一般是从根节点一路遍历到叶节点，于此同时顺便初始化，即把类似 f [ u ] [ v ] [ 1 ] 的迭代基础给打好，或者在所有操作前就做好初始化

   • 从叶节点到根：

     一般来说这是一个状态转移的过程，即类似 f [ u ] [ v ] = max ( f [ u ] [ v ] , f [ u ] [ k ] + f [ k + 1 ] [ v ] +somethings ) 的过程

   • 一般存的是单向图，毕竟是一棵树
   • 树形DP中遍历的顺序主要与存边顺序有关
   • 如果是无向图，就使用child和father的方法遍历图
   • 不一定都是先遍历后DP，看实际情况 [ USACO10MAR ] Great Cow Gather

     解题报告：

Type 【1】 选课

• 前言：

  难受，香菇 ——王夫斯基

• 可以说是很经典的树形DP题目了

• 这里实际上就是一个拓扑关系：只有执行了上一个，才能执行下一个

• 其中还包含一个森林，即最终的祖先不一样，可以建立 0 为一个虚拟节点，作为所有森林的祖先

• 心路过程（有进步）：

  1. 这个好像就是区间最大和啊
  2. 而且还有强调 m 段
  3. 估计是类似 f [ u ] [ v ] [ i ] = max ( f [ u ] [ v ] [ i ] , f [ u ] [ k1 ] [ j ] + f [ k2 ] [ v ] [ i - j ] ) 的形式吧
  4. 其中k1和k2是指一个中继点，类似Floyd
  5. 而且肯定可以用某种迭代顺序降维（参见【学习笔记——区间DP】中的分成m段的思路）
  6. 耗了很多时间，结果k1和k2就是不懂怎么表示
  7. 我羞耻地败了（明明是日常操作好吗）

• 题解过程：

  1. 按存图的顺序给每个节点一个编号，从1~n+1
  2. 设 f [ u ] [ j ] [ k ] 表示以u为根节点的子树，考虑前j个节点选k门课的方案数
  3. 迭代起始为：f [ u ] [ 1 ] [ 1 ] = val [ u ] )
  4. 则状态转移方程为f [ u ] [ j ] [ k ] = max ( f [ u ] [ j ] [ k ] , f [ u ] [ n ] [ l ] + f [ v ] [ j - 1 ] [ k - l ] )
  5. 当然了，我要用到j-1的内容，都是满足l<k的，所以倒着循环k，这样就可以使我们在一个数组中当前值和上面我们用到的值完全不影响
  6. 所以

           for ( k = m + 1 ; k > = 1 ; k -- )
               for (  l = 0 ; l < k ; l ++ )
                   f [ u ] [ k ] = max ( f [ u ] [ k ] , f [ v ] [ l ] + f [ u ] [ k - l ] )

  7. 事实上手膜一下就可以发现，从大到小迭代，能保证有解可转移，如果满足条件就可以覆盖，何乐而不为呢
  8. 得解

Type 【2】 [ ZJOI2008 ]骑士

• 前言：

  基……基环树真是个好东西——王夫斯基

• 状态方程和转移方程都很简单的啦
• 真不骗你，和【[ 福建省历届夏令营 ] 没有上司的舞会】几乎一毛一样
• 但我们发现，咦……
• 肿么有环呢，而且只有一个环，要怎么处理呢？
• 考虑删边和补边
• 对每个root保存他们的father，通过循环找到形成环的最后那一条边，在不连它时，作一遍DP，连了它之后，再做一遍DP，取两个f的最大值，保存为ans
• DP操作时，遍历到尽头，f [ v ] [ 0 ] 赋一个负值，初始化，不一定要赋值
• 真是抱歉呢，赋值是一定要赋的，因为把最后一个点设为-INF，其实就是删边操作
• 需要注意的是，由于要进行多次DP，最好在遍历图时才更新f [ u ] [ 1 ] 和 f [ u ] [ 0 ]
• 当然了，要对每个节点都找环，如果在已找过的环上,有flag [ i ] == 1，就不再加和了，如果那个点不在环上，肯定要对它再进行DP，找环，以确保每个“骑士”都能被“青睐”过

Type 【3】 [ USACO10MAR ] Great Cow Gather

• 前言：

  好东西，你没有玩过的船新版本——王夫斯基

• 首先看到n<=1000000，就可以知道，不是一维的状态方程，就是其他什么贪心啥的
• 于是我想，估计用 f [ i ] 表示剩下n-1个节点到i节点的代价
• 一定可以用其他f [ i ] 转移过来，删掉一条边，再加回去？
• 然后我又想，如何实现呢
• 我没了
• 其实，想一想，有这么个情况：

① 所有的牛首先到达了1号节点

② 3号节点以及他子树上的节点都需要退回1->3的路径的长度

③ 除了3号节点以及他子树上的节点都需要前进1->3的路径的长度

• 从1这个点开始DP
• 也就是作两遍dfs就行了，DP只是用于状态转移的
• 而且是存无向图，用child和father的遍历方法来遍历
• 第一次dfs，求出到每个点i的后代们到节点i的奶牛数，以及后代们到i的代价之和d [ i ]
• 把每个f [ i ] 赋值d [ 1 ]，因为都是从节点1往下DP
• 第二次dfs计算偏移的值，即一退一进

  f [ v ] = f [ u ] - Count [ v ] * s + ( sum - Count [ v ] ) * s

• 当然，直接把d [ i ] 赋值过去会使得f [ i ] 很大,还多个O(n) 时间
• 那就先不赋值f [ i ]，最后再加上d [ i ]
• 得解

Type 【4】 [ SDOI2011 ] 消耗战

• 前言：

虚……虚树优化？！——王蒟蒻

• 首先我们先讲一下暴力一点的DP
• 对每个查询点，我们肯定知道，要割掉它的最小代价，是它到1的最小边
• 而且如果有多个查询点j通过一个查询点i链接到1,那么割掉它们有两种方法：

1.割掉 i，其实它们就都被割掉了，代价为f [ i ]

2.对一些 j 进行割边，将代价累和∑f [ j ]

• 然后对它们求min
• 当然，求割掉i,是从根到叶的操作，毕竟只有它前面的边才对它有作用，所以放置在DP ( v , u ) 的前面
• 未到达查询点时，就把每个点到1的最小边找出来
• 到达查询点时，就把u->v的边权加入temp，跳过该循环，毕竟再往下已经没什么意义了
• 然后就是对j那些点进行割边，是从叶到根的操作，因为要加和，把f [ v ] 加到temp上去，temp就相当于把j割掉的代价的总和
• 最后退出遍历时，对f [ u ] 和temp取min就好了
• 所有的答案都汇总到f [ 1 ] ，输出f [ 1 ] 即可

  重点来了，这道题的DP是容易的，但优化却很难

• 想想看，那么多个点，每次才查询k个点
• 是不是浪费时间到不可接受
• 应此，我们应该对其进行虚树优化，把关键点保留（即查询点和它们的LCA）
• 首先先建一个原图e，对原图求dfs序期间可以顺带初始化LCA 即dfn[i]，然后对每个查询点 note [ i ] 都按照dfn从大到小排序
• 然后往栈顶放入note [ 1 ]
• 开始从2->k迭代，求note [ i ] 与 栈顶元素的LCA即lc
• 接下来要开始重要操作了：

1. 如果depth [ lc ]>=depth [ s [ top-1 ]:

a. 如果lc==s [ top ]:

那什么都不用操作，因为剪掉栈顶元素同时也剪掉了lc

b. 如果不是：将lc与s [ top ] 连起来 ，若lc!=s [ top - 1 ]，它一定在s [ top ] 和 s [ top - 1 ] 之间：

如果lc == s [ top - 1 ]:

把栈顶元素弹出即可

2. 如果depth [ lc ]<depth [ s [ top-1 ]:

从stak [ top − 3 ] −> stak [ top − 2 ] −> stak [ top − 1 ] −> stak [ top ] 变成了stak [ top − 3 ] −> lc −> a。我们需要循环依次将最右链的末端剪下，将被剪下的边加入虚树，直到不再是该情况。

就上图而言，循环会持续两轮，将stak [ top ] ,stak [ top − 1 ]次出栈，并且把边tak[top−1]−>stak[top],stak[top−2]−>stak[top−1] 加入虚树中。随后通过情况二完成构建。 即把

Add(s[top-1],s[top]);  
                    top--;

3. 最后统一把a压入栈中

• 重要操作结束后，把栈中相邻两个节点建树

• 输出dp( s [ 1 ] )

• 注意：不能直接对图进行清空，否则复杂度会退化到O(n)的复杂度，这是我们无法承受的。在dfs的过程中每当访问完一个结点就进行清空即可。

• 由于这题太变态，我给出代码