省选前做题

ABC306Ex Balance Scale

先考虑没有 = 的情况。

此时相当于给无向图定向为 DAG 的方案数。

仿照拓扑序的过程：每次钦定一个极大的入度为 $0$ 的点集，然后把点集里的所有边定向，注意这里的点集必须是独立集。

问题是我们并不能保证极大，所以会算重。

对于当前的全集 $S$，每个入度为 $0$ 点集 $T$ 的贡献会被所有 $T' \subseteq T$ 多算一遍。

所以容斥系数 $g$ 需要满足 $\sum_{T'\sube T}g(T')=1$，手玩发现 $g(T')=(-1)^{|T'|+1}$。

转移方程 $f_S=\sum_{T\sube S}[\text{T is an independent-set}](-1)^{|T|+1}f_{S/T}$。

现在加上 =，也就是说可以出现环了。

于是在枚举 $T$ 的时候不需要枚举独立集，把 $T$ 之间的边看作 =。容斥系数跟着变为 $(-1)^{T 的联通块数+1}$。

复杂度 $O(2^n+3^n)$。

APC001A XOR Tree

令 $u$ 的邻边异或和为 $a_u$，所有边边权为 $0$ 等价于 $a_u$ 全部为 $0$。

每次操作可以选择 $a_u\larr a_u \oplus x,a_v \larr a_v \oplus x$。

贪心，如果有相同的 $a_u$ 直接抵消。然后最多剩下 $15$ 个非零数，设为集合 $S$。

设 $f_S$ 表示把 $S$ 集合消完的最小步数，下界为 $|S|-1$。

转移考虑把 $S$ 分为两个异或和分别为 $0$ 的子集，$f_S \larr f_{T}+f_{S/T}$。

QOJ5357 芒果冰加了空气

理解起来困难的一道题。

记原树中 $u$ 的子树为 $tree_u$。

考虑两棵子树的点分树如何合并。（注：以下的“树”基本指点分树）。

反向考虑，一棵树如果从 $(u,v)$ 断开，它的点分树如何分裂。

先确定两棵树的根，不妨设原来的根在 $tree_u$ 内，那么 $rt_u$ 为原来的根，$rt_v$ 是点分树中在 $tree_v$ 内深度最小的点。

只有在 $tree_u,tree_v$ 之间左右横跳的边会被影响。不难发现这些边都在一条链上，这条链过 $rt_u,rt_v,u,v$。

如何把这条链拆成两条分别在 $tree_u,tree_v$ 里的链呢？

很简单，在不改变顺序的情况下，将原本在 $tree_u$ 内的点首尾相接，$tree_v$ 中的同理，形成两条 $rt_u \rarr u,rt_v \rarr v$ 的链。

不难发现这样生成的两棵点分树依旧合法。

接下来考虑这个操作的逆过程：类似地，在不改变两条链顺序的前提下，将两条链以任意顺序合并，方案数为 $\binom{len1+len2}{len2}$。

发现合并方案数只跟两条链的长度有关，于是设 $f_{u,i}$ 表示 $u$ 的点分树中 $u$ 的深度为 $i$ 的方案数。

树形背包转移，$f'_{u,x} \larr f_{u,i}\times f_{v,j} \times \binom{x-1}{i-1},j \ge x-i$，实现时可以把 $f_v$ 后缀和处理。

• 为什么不是 $i,j$ 转移到 $i+j$ 呢？因为我们只关心 $rt \rarr u$ 的路径长度，在合并后的链上排在 $u$ 后面的点不计入 $x$。
• 为什么系数不是 $\binom{x}{i}$ 呢？因为 $u$ 必须排在 $rt \rarr u$ 路径的最后一个。

QOJ9904 最小生成树

称 type-i 类型的边为所有满足 $x+y=i$ 的边 $(x,y,a_i)$。

还是用 kruskal，每次找到最小的一类边，把这类边能连的（不在同一并查集里的）都连上。

如何找到所有可以连的边？考虑用二分加速，每次判断两段区间的并查集编号是否一一对应。这个可以用线段树维护哈希。

瓶颈在并查集启发式合并里维护线段树，复杂度 $O(n \log^2 n)$。

P5443 [APIO2019] 桥梁

操作分块。并查集，查询每个点所在联通块大小。

将所有边和询问按重量降序排序。处理到一个询问时把权值不小于它的边加入并查集。

对于块外的边，提前处理好。对于块内的边，每次暴力找那些可以加入。

CF1534F2 Falling Sand (Hard Version)

称第 $i$ 列倒序第 $a_i$ 个点为关键点 $i$。

将干扰关系建图，强连通缩点。称 $u$ 覆盖 $v$ 当且仅当从 $u$ 出发能到达 $v$。

目标：选取最少的点，覆盖所有关键点。

先删除所有能被其他关键点覆盖的关键点。

不难发现每个点覆盖的关键点是一段区间。

证明简单，如果存在关键点 $x<u<v$ 使得 $v$ 被 $x$ 覆盖，$u$ 不能。那么 $x$ 到达 $u$ 的时候高度 $<a_u$，所以 $u$ 覆盖 $v$，矛盾。

DAG 上 dp 求出每个点能覆盖的区间，然后贪心。

CF1019C Sergey's problem

如果是无向图怎么做？

选出一个极大的独立集即可。可以满足任一点一步到 $S$ 中的点。

现在考虑有向图。还是用刚刚的做法。每选一个点 $u$，就把 $u$ 的所有出边的端点 $v$ 打上标记。

刚刚的性质还是满足，只不过 $S$ 的导出子图 $G'(S,E')$ 可能会存在一些满足 $u$ 在 $v$ 后标记的边 $(u,v)$。

显然 $G'$ 是一个 DAG。我们对 $G'$ 按拓扑序从小到大再做一遍刚刚的贪心，最后得到 $S'$。

为什么 $S'$ 能满足题目的条件呢？

1. $S'$ 是独立集，因为我们钦定了贪心的顺序。

2. $S$ 中的点能一步走到任意一点，而 $S'$ 中的点能一步走到 $S$ 中任意一点。

   所以 $S'$ 中的点能两步走到任意一点。

CF1578J Just Kingdom

令 $siz_u$ 表示 $\sum_{v\in tree(u)}m_v$。

考虑对于一个点 $u$ 怎么算答案？

观察如果 $u$ 的子树想获得 $x$ 的钱（$x\le siz_u$），$fa_u$ 至少要获得多少钱。

对于 $u$ 的兄弟 $v$，若 $v$ 被填满，则 $v$ 的子树获得了 $siz_v$，否则获得了 $x$（要满足平均分配原则）。

于是，当 $u$ 转移到 $fa_u$ 时，$x' \larr \sum_{v\in son_{fa_u}}\min(x,siz_v)$。

现在我们会对每个 $u$ 分别 $O(n)$ 算答案了，只需要不断跳祖先即可。

考虑在 $u$ 处维护 $u$ 子树内的全部答案。

维护 set $s_u$ 储存子树内的所有询问 $(x,y)$。表示从 $y$ 开始跳，跳到当前点时答案为 $x$。

将当前点的所有儿子 $siz_v$ 排序。发现 $s_u$ 中每个 $x$ 的变化形如 $x' \larr kx+b$。

进一步，发现 $x$ 在跳祖先的过程中 $k \ge 2$ 的情况不超过 $\log V$ 次。

于是我们手动处理所有 $k \ge 2$ 的情况，其余情况打 tag。

合并 $s_u$ 时启发式合并就行啦。