分治套 NTT 优化仙人掌 DP 题目。往这个方向想其实不是很难推,于是就懒得写题解直接贴代码了 qwq。

虚树学习笔记

题目先给定一棵树,然后每次询问和其中的一部分点有关的信息,且只考虑这些点和他们的 LCA 对答案没有影响,则可以考虑虚树。先求出所有点的欧拉序,把每次询问给出的点按照欧拉序排序,依次插入栈中,维护栈内元素使得形成一条在已插入的点中最右端的链。

其实没什么新知识,可以说是一种思想,所以代码也很好写,就是需要注意细节。

CF1059E - Split the Tree

一个永远只能在考完后调出 Codeforces 的题的菜鸡厚颜无耻得跑来写题解了。。。

本题要求把树分成的链必须是垂直路径,也就是说不能同时跨越一颗子树的两个根。也就是说每次选中的路径都是到根节点的一串。

所以我们可以通过树上倍增预处理出每个节点 $u$ 如果被选中那么最多可以向上形成长度为 $dp[u]$ 的链。接着跑一遍树上 DP 即可。

预处理时间复杂度 $O(n \log n)$ ,树上 DP 时间复杂度 $O(n)$ 。

貌似因为 D 题比较难调试,做这题的人比较少?反正我这种菜鸡就算考场有时间写了估计也调不出来吧。

UVA1220 - Party at Hali-Bula

用 $f[i][0]$ 表示 $i$ 不选所能取到的最大值, $f[i][1]$ 表示选 $i$ 能取到的最大值。

假设当前节点为 $u$ ,孩子节点为 $v$ ,则:

  • $f[u][0] = \sum\limits_{v \in son[u]} \max(f[v][0], f[v][1])$
  • $f[u][1] = \sum\limits_{v \in son[u]} f[v][0]$

关于判断是否有多种情况:我们无需存种数,只要存是否即可,用数组 $d$ 表示,则:

  • 如果当前节点 $u$ 更新状态选中的来自 $v$ 的某个状态存在多种,那么 $u$ 的这个状态也存在多种。
  • 如果 $u$ 节点的某个孩子 $v$ 满足 $f[v][0] == f[v][1]$ ,那么 $f[u][0]$ 存在多种。

洛谷2996 - 拜访奶牛

首先,这题无法用贪心实现,下面是一个反例:

贪心反例

贪心的话最大值是 $5$,然而可以在中途放弃一个点从而取到最大值 $6$ 。

我们使用 $f[i][0]$ 来表示到第 $i$ 个点但不取这个点所能获得的最大值,用 $f[i][1]$ 表示到第 $i$ 个点且取这个点所能获得的最大值。

先将每个点都DFS遍历一遍,在回溯时进行DP( $u$ 是当前节点,$G[u][i]$ 是孩子节点):

  • 如果当前节点不选,那么孩子节点选或不选均可
    $f[u][0] += max(f[G[u][i]][0], f[G[u][i]][1]) $

  • 如果当前节点选中,那么孩子节点只能不选
    $f[u][1] += f[G[u][i]][0] $

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×