DFS序列（$\mathrm{dfn}$）
在没有或存在一定限制条件的情况下，以DFS遍历经过的节点顺序构成的序列。记$\mathrm{dfn}(x)$为第一次访问该节点的时间戳，$\mathrm{seq}(t)$为访问序为$t$的节点。
容易发现，节点$x$的子树节点的$\mathrm{dfn}$一定是一段连续的区间。故我们可以使用数据结构方便地维护子树的信息。
标签： DFS
-
AcWing 169 16×16数独 – 代码
对，这真的只是为了纪念调试了半天多才通过的这道毒瘤题目的。码长$5\textrm{KB}$。
剪枝框架是按照《进阶指南》写的，但具体实现仍然沿用了九宫格数独的方法——分别记录每一行、列、十六宫格的可填入数字的二进制数，然后取与运算。所以相对来说没有那么直观。
-
洛谷题库 P2414 [NOI2011] 阿狸的打字机 简略题解
根据题意，这是一道多模式串多文本串匹配问题。容易想到AC自动机。易知第一行的输入可以用递归/栈的形式模拟并且构建一棵Trie，可以在$\mathrm{O}(|S_0|)$的时间内完成。可以同时构建Fail失配树，时间复杂度$\mathrm{O}(P)$，$P$为Trie的节点总数。
-
洛谷题库 P3304 [SDOI2013]直径 题解与思路重现
想看正解请直接跳过文章前半段。
不知道到底错没错的错解这是一道树的直径的必经边问题。
单单求树的直径是非常简单的。可以通过两次DFS/BFS或一次树形DP完成$\mathrm{O}(N)$的求解。显然，树的直径长度唯一，但构成该长度的链的方案可能不唯一。