日记

社会主义好~~~

HOT-Hotels 加强版# Link to

我们首先有朴素的 dp：$dp1_{u,i}$ 表示 $u$ 子树里有几个点离 $u$ 的距离是 $i$。$dp2_{u,i}$ 表示 $u$ 里有多少个点对 $(u,v)$，使得 $\text{dis}(u,\text{lca}(u,v)) = \text{dis}(v,\text{lca}(u,v)) = \text{dis}(u,\text{lca}(u,v)) + i$。

考虑如何转移。$dp1$ 的转移十分简单：$dp1_{u,i + 1} = \sum_{v \in son(u)}dp1_{v,i}$。如何转移 $dp2$ 呢？可以归类为两种情况：

• 之前子树和当前分别贡献一个点：
  $dp2_{u,i + 1} \gets dp1_{v,i} \times dp1_{u,i + 1}$
• 这个子树贡献两个点：
  $dp2_{u,i - 1} \gets dp2_{v,i}$

记得先转移 $dp2$ 再转移 $dp1$，不然会造成重复转移。

显然这玩意是 $O(n^2)$ 的，考虑如何优化。我们发现一种叫 长链剖分 的东西，可以用来优化下标是深度的 dp。考虑只有一个子树的时候 $dp1$ 和 $dp2$ 如何转移。发现是这个样子的：

聪明的你肯定就能发现：这玩意可以用指针实现 $O(1)$。具体实现如下：

1
2
3
4

int pool[maxn << 2],*dp1[maxn],*dp2[maxn];

dp1[v] = dp1[u] + 1;
dp2[v] = dp2[u] - 1;

这个转移完了，其他的暴力转移就是了。因为所有长链的总长度是 $n$，所以复杂度也就是 $O(n)$ 的。

购票# Link to

首先有暴力 dp：设 $dp_u$ 表示到 $u$ 的最小代价。有显然的转移：

零帧起手推式子哈

发现长得就很斜率优化。但是树上显然不好做单调栈，所以直接上树。
套上斜优 $y = kx + b$：

然后就可以兴致勃勃的开始打代码了。打到一半你会发现：这个 $l_i$ 是干什么事的？啊原来还有个沟槽的 $l_i$ 的限制啊？？？

考虑如何处理这个限制。我们观察题解得到：有个东西叫做出栈序。我们可以在出栈序上二分出最后一个 $\text{dis}(u,v) \le l_i$ 的祖先 $u$，于是我们就可以愉快的写个线段树套李超树。因为只能查询一个区间内的线段的最小值，所以只能套个线段树。

小 N 的独立集# Link to

是这个小 N吗？

神秘 dp 套 dp。

考虑如何求最大独立集。设 $dp_{u,0}$ 表示强制不选，$dp_{u,1}$ 表示可选（不一定选）转移是显然的。但是我们发现 $n,k$ 都十分的小啊。所以我们可以考虑把他们塞到状态里。

但是我们发现这玩意根本存不下，但是，我们有个性质：$dp_{u,0} \ge dp_{u,1} - k$。我们就可以优化状态，从而优化复杂度了。

后日谈 # Link to 后日谈

社会主义好~~~