BZOJ5404 - party

和其他题解不太一样,这里没有用线段树……

首先肯定会在 LCA 处集合,通过树剖 + bitset 维护出可选的集合。然后利用 Hall 定理进行完美匹配统计答案。可以发现直接树剖 + 暴力跳是 $O(n ^ 2)$ 的,所以限制树链的长度至多为 $S$ ,则复杂度为:$O(n + qcS\times\frac{m}{32} + qc \times \frac{n}{S} + q \times 2^c \times \frac{m}{32})$ ,取 $S = \sqrt n$ 。

然后跑的飞快 233333.

本题有虚树做法,基本思想差不多,但个人感觉还是换根树剖清真一点 233。

定义一组询问的根节点为这组询问的一号节点。

一个点会对答案产生贡献,当且仅当这个点到这组节点的其他节点的距离大于等于这个节点到这组询问的根节点的距离。

假设当前我们做到根节点为 $ root $ ,当前节点为 $ u $ 的情况,找出这条路径的中点为 $ mid $ ,那么肯定不会对答案产生贡献的点即整颗树 $ root $ 为根节点时 $ mid $ 这个节点的整颗子树。就是一个简单的换根树剖,乱搞一下即可。

按题意可知,考虑每个节点会给左孩子带来一个 $(-\infty, a_i )$ 的限制,会给右孩子带来一个 $(a_i, +\infty)$ 的限制。 定义限制 $(-\infty, a_i)$ 的限制取反为 $(a_i, +\infty)$ ,反之亦然。

考虑把原树进行树链剖分。每个节点存放自己给重儿子带来的限制,用支持单点修改、区间取反、区间查询的线段树维护区间限制的并集。由于每个节点往上跳只会经过 $\log n$ 条重链,重链内部直接从线段树上查询,两条重链之间的转移把转折点对重儿子的限制取反即可。总复杂度为 $O(n \log ^ 2 n)$,可以通过此题。

动态 DP 学习笔记

(好懒不想写博客)

把每个点的 dp 转移分成 重儿子 和 自己+轻儿子 两个部分。重儿子的转移把矩阵放树上维护,利用矩阵乘法的性质;轻儿子的转移的每次修改时暴力维护,利用 dp 的性质。详情参考 txc 哥哥的博客

洛谷4949 - 最短距离

本题大概是一个基环树上带修改边权的最短距离。可以把他看做一棵树,把多的那条边拎出来,树剖维护距离,分类讨论即可。大概是你谷蓝题难度吧。

由于树剖只需要查询 dfs 序上区间最小值,可以考虑树状数组维护常熟较小。目前不卡常的情况下你谷效率 rk1 。

这题洛谷的数据太…水,克鲁斯卡尔重构树不连通都可水过。

  • 3545: [ONTAK2010]Peaks
  • 3551: [ONTAK2010]Peaks加强版

在线算法:克鲁斯卡尔重构树套主席树。

在克鲁斯卡尔重构树上维护 DFS 序(或树链剖分)再套上主席树,维护第 $k$ 大。

当然非加强版由于你是重构树(被针对了)可能要大力卡常。比如加个 fread 以及离散化一下什么的。

Your browser is out-of-date!

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

×