CF1494D Dogeforces CF1494D Dogeforces 发现我们最终维护出来的树肯定是一个大根堆的样子，也就是父亲节点的权值严格大于子树的任意节点的权值，那么既然所有叶子节点的关系边权都已经给出了，我们不妨考虑使用 $\tt Kruscal$ 重构树进行构造。 但是重构树可能存在一种情况，也就是父亲节点的权值和儿子节点的权值是相同的，我们不妨考虑将这两个点缩成同一个点。 我们考虑这种构造是否合法，也就是是否仍然满足二叉树的性质，如果当前的点和父亲节点缩到一起的话，可以保证每个节点至少有两个儿子，正好和题目的要求相契合。 显然如果说恰好只有 $2$ 个儿子的话显然不能用构造，考虑树： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#i ...

论小部分的图树论转化 Graph 直接将模型抽象到图上：比如说题目说了相互之间的关联，可以直接看做边之类的。 同类（相同集合）建图：如果说需要求一个集合满足 $\forall a \in S$ 都存在一个不同的 $f(a) \in S$，对于这种我们可以考虑将 $a \to f(a)$ 这样的话如果出现了环就说明是本质相同的。 我们也不一定要局限于这样的函数，比如说求 $\sum_{i \in S} i - a_i = 0$ 中的 $S$，我们不妨考虑将其分开来考虑 $\sum_{i \in S} i = \sum_{i \in S} a_i$ 那么限制的本质就是一个满射，而且属于同一个域（封闭性）。那么我们考虑建边 $i \to a_i$ 找到合法的环即可。 前缀和优化建图：如果需要考虑连边关系的时候，我们考虑将 $i$ 可以到 $j$ 转化成**存在一条 **$i \to j$ 的路径即可，不一定需要直接连边。换句话说，只要我们建立的图进行传递闭包之后满足上述条件即可。 前缀和作差建图：不妨考虑题目中给定进行一个操作的限制是，区间和为 $0$。那 ...

CF1601C Optimal Insertion [CF1601C](C. Optimal Insertion) 我们不妨考虑让 $b$ 先进行排序从小到大进行插入。 考虑相邻两个位置的 $b$，不妨考虑为 $i, i + 1$。显然 $pos_i < pos_{i + 1}$，不然交换之后肯定可以得到更优的答案。 我们考虑既然有单调性，就可以进行分治。 我们考虑进行像 $\tt Dp$ 一样进行决策单调性分治，之后需要在 $O(n)$ 内算出 $b_{mid}$ 的最优位置。 我们不妨考虑钦定一个逆序对的基准值，之后每次移动 $b_{mid}$ 的位置都修改贡献，具体来说： $a_i < b_{mid}$ 就需要减少贡献。 $a_i > b_{mid}$ 就需要增加贡献。 之后我们只要建出序列直接进行计算即可。 复杂度 $O((n + m) \log n)$。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535 ...

三元环计数 就是考试的时候整了一个这个科技，我没想出来，然后无了… 具体来说就是计算图中三元团的个数。 有一个 $O(m\sqrt m)$ 的算法： 让度数大的点连接度数小的点。 枚举每个点并将其相邻的点记录匹配点为当前点 $i$。 枚举当前点邻居的邻居，看匹配点是否是点 $i$。 每个三元团只会被计算一次。 分析一下复杂度： 每个点的入度度数最大是 $O(\sqrt m)$，这里可以考虑反证： 如果大于 $\sqrt m$，那么连边就是不合法的。 所以打标记是 $O(m\sqrt m)$ 的。 为了保证图是一个 $DAG$ ，我们还需要钦定如果度数相同要从值小的连接向大的即可。 这样可以保证一个三元环 $(u, v, w)$ 被计算当且仅当存在边：$u \to v, u \to w, v \to w$。 $Code$ 12345678910111213141516for(int i = 1; i <= m; ++ i) r1(eu[i], ev[i]), ++ deg[eu[i]], ++ deg[ev[i]];auto cmp = [&](int a, ...

P3366 【模板】最小生成树这个算法就是考虑每一次合并 $n$ 个联通块，变成 $\frac{n}{2}$ 个。所以总共合并的次数是 $\log_2 n$ 次。 我们还是使用并查集来维护每一个联通块，这个算法的好处就是因为其合并次数是 $\log n$ 级别的，所以我们可以在里面进行 $O(n)$ 的处理。来处理一些不能直接进行最小生成树的情况。 比如说要维护两点 $\tt And$ 值为 $0$ 的图。我们直接使用 $\tt prim$ 复杂度会直接爆炸。但是我们用 $\tt Boruvka$ 可以每一次 $O(n)$ 级别处理各种联通块的信息，然后进行生成树。 对于模板题具体来说，我们对于每一个联通块维护一个最小的边权，边的另外一头是与其所属联通块不同的点。 这边注意每一次操作应该考虑的是所属联通块，然后这边有一个很好的性质 可能也没有那么有性质。 $\color{red}\tt \text{在进行合并联通块之前，联通块的根是不会变的}$。 这样我们可以直接在预处理的时候存储每个集合的根，看起来这个性质不起眼，但是在题目中可以方便许多。 123456789101112131 ...

浅谈AC自动机 建议学过 AC 自动机的人来看。 注意我们一开始直接建立串的时候是 $\tt Trie$ 图，之后建立 $\tt fail$ 指针的时候才是真正的 $AC$ 自动机。 具体来说对于 $\tt Trie$ 上深度从小到大的一条链，对应的是一个曾经在某个或者多个串中出现过的子串。 如果说是一条从根到底的链那本质就是代表一个串，显然对于一条链之间的点，本质上深度小的是深度大的前缀串。 用处： 我们可以通过遍历 $\tt Trie$ 图来不重复地遍历每个字符串（不会有相交）。 还有一个东西叫 $\tt fail$ 树，这个东西的定义和 $\tt nxt$ 数组很类似，就是与当前串公共后缀最长的点。 那么我们一直沿着 $\tt fail$ 树跳的话是可以遍历到所有与当前串后缀部分有交的串，而且是交是从大到小的。 注意： 我们进行找 $\tt fail$ 指针的时候需要使用路径压缩，但是即使使用了路径压缩，我们直接建立 $\tt fail$ 树的时候完全不会有影响。 如果说拿节点 $1$ 当做超级源点的话，对于周围一圈的不存在的点，需要路径压缩至点 $1$。 用 ...

浅谈欧拉路径，欧拉回路 引入前有哈密顿路径，表示经过每个点恰好一次，现有欧拉路径，表示经过每条边恰好一次。 许多题目重要的是建模，往往最浅的建模就是点之间的连边，表示可以到达。如果说需要满足到达每个点一次，这就变成了 $\tt NPC$ 问题。但是我们往往可以将一个信息拆分成若干个信息，变成边之间的关系，这样就有多项式复杂度的解法，同样这个是可以求方案的。 本篇会向读者介绍欧拉路径和欧拉回路以及其判定方法，还有常用的套路。 欧拉图具有欧拉回路的图叫欧拉图，如果只有欧拉路径就叫做半欧拉图。 欧拉路径定义：经过每条边恰好一次，起点和终点不一定相同。 无向图每个点的度数都是偶数，或者只有两个节点度数是奇数。 有向图设一个点的权值 $v_i$ 表示其出度减去入度。 那么存在的欧拉路径的条件是 $v_i = 0$ 或者同时存在一个 $v_i = 1, v_j = -1, i \ne j$。 欧拉回路定义经过每条边恰好一次，起点和终点相同。 无向图每个点的度数都是偶数。 有向图设一个点的权值 $v_i$ 表示其出度减去入度。 那么存在的欧拉路径的条件是 $ ...

浅谈 Wqs 二分 主要是今天写 「九省联考 2018」林克卡特树 的时候遇到了，就学一下。 使用条件 题目中对于一种 $\tt Dp$ 有限制，但是如果没有限制，其复杂度是正确而且很好求的。举个例子来说： 将一棵树划分成 $k$ 条链，我们 $\tt Dp$ 的时候只需要记录当前节点是否被匹配过，以及是否正在被匹配即可，而且我们还要考虑总共有几条链，进行划分。但是如果不考虑链的数量，这个 $\tt Dp$ 显然是 $O(n)$ 的。 对于背包类型的 $\tt Dp$ 来说如果有物品数量的限制，之前常常会有 $O(n^2)$ 不得不枚举的复杂度，我们将其消去常常就可以得到正确的复杂度。 对于限制的依赖，可以考虑限制是 $x$，贡献是 $f(x)$，对于点对 $(x, f(x))$ 其构成一个凸包。 具体实现对于一个凸包考虑枚举斜率进行切割，对于一个上凸包来说斜率是从左到右逐渐递减的。 我们考虑枚举一个斜率 $k$，那么我们的截距是什么呢，显然就是 $f(x) - kx$。 显然对于所有的 $g(x) = f(x) - kx, (x, g(x))$ 同 ...