圆方树
圆方树能有效地把图论问题转换为树上问题，从而利用数据结构高效地维护信息。
考虑对一个无向图建出它的圆方树，这棵圆方树上的点分为两种：圆点与方点。
我们首先对于无向图的每一个点双连通分量新增一个方点，将该方点与连通分量中的每一个点相连，断开原图所有边。
比如该图：
建出其圆方树：
其中节点 \(8,9,10\) 为方点。
首先建出圆方树，那么答案就是两个节点之间的圆点个数。
建出圆方树之后，考虑固定 \(c\)，考虑点对贡献。对于一个点，拆分为子树内的点相互产生的贡献和子树内与外的点产生的贡献，\(dfs\) 即可解决。
建出圆方树，首先考虑对于每一个方点维护与他相连的圆点的权值最小值，发现修改操作无法进行。
那么考虑对于每一个方点维护一个 \(\text{multiset}\)，存储与其相连圆点的权值，每次修改圆点，暴力修改与其相连方点的 \(\text{multiset}\)。
发现可以被菊花图卡，然后我就不会做了。
原来可以对于每一个方点，只维护其儿子圆点的 \(\text{multiset}\)，然后线段树求最小值，如果要旅行的两个点的 \(\text{LCA}\) 是方点，要额外考虑其父亲圆点的贡献。
UVA1464 Traffic Real Time Query System
建出圆方树，与 P4320 道路相遇 处理相同，唯一变化的是询问转换为边，则我们每次询问对于两条边 \(u[x],v[x],u[y],v[y]\) 中不属于同一条边的两个节点两两询问取 \(\max\) 即可。
模拟退火
模拟退火是爬山算法的升级版，爬山算法适用于处理单峰函数问题，而出现非单峰函数的题目时，爬山算法会陷入局部最优解。这时候使用模拟退火，能有概率避免陷入局部最优解的情况。
线段树优化建图
有一些图论问题的时间复杂度瓶颈在于连边，例如需要将区间 \([l_1,r_1]\) 与区间 \([l_2,r_2]\) 中的点相连，这时复杂度到达了 \(O(n^2)\)，所以我们考虑优化建图这一过程来优化复杂度。
在针对区间问题，我们考虑用线段树这一解决区间问题的有力工具来优化建图，考虑建立两棵线段树表示出树与入树。
对于出树，考虑对于出树上的区间节点，对于它的左，右区间，向当前区间节点连边。
对于入树，对于当前的区间节点，向它的左，右区间连边。
然后我们分成 \(4\) 类讨论：
对于点向点连边，直接在出树与入树上找到对应的叶子节点连边。
对于区间向点连边，在出树上找到对应区间向对应叶子节点连边。
对于点向区间连边，找到对应叶子节点向入树上对应区间连边。
对于区间向区间连边，我们新增节点 \(node\)，出树对应区间向 \(node\) 连边， \(node\) 向入树对应区间连边。
最后我们就达到了优化建图的目的。
AC 自动机
\(tr[i].end\) 为 \(1\) 时表示为该节点为串尾。
\(tr[i].sum\) 表示以该点为串尾的字符串数。
普通自动机
考虑对模式串建出自动机，在串尾打 tag ，在文本串上跑自动机，开一个栈维护当前位跑到自动机上的节点编号，一个栈维护剩余的字符，当跑到串尾时，弹出该串所有的字符，挂在自动机上的指针回退到该串入栈之前。
考虑将 \(t\) 拆成两半，枚举断点，设 \(t=t_1+t_2\)，则只需要考虑模式串分别匹配 \(t_1\) 的后缀与 \(t_2\) 的前缀即可。
由于自动机的 fail 指针有着优秀的后缀性质，所以我们可以将模式串与文本串以正序和逆序分别建出两台自动机，这样前后缀的问题就解决了。
由于 fail 指针代表着当前字符串的后缀子串，所以我们在累加贡献的时候串的贡献要加上其后缀子串的贡献，这一步可以在求 fail 指针时求出来。
对 fail 树的操作 + DS 维护
考虑建出该字典图的 fail 树，考虑 fail 树的性质。由于串长不超过 \(20\)， 在每一个节点维护一个状压集合 \(S\) 表示从根到该节点的所有串能匹配的长度，考虑边 \(u->v\)，下传时显然有 \(S_v~|=S_u\)，特殊的，若该节点本身是串尾，则 \(S_u~|=(1<<dep_u)\) 。
考虑依旧使用状压来匹配，在字典树上跑当前的文本串，记录跑到的节点到根节点中的串尾的长度，也能用状压维护，最后把两个值与起来不为 \(0\) 就能计入答案了。
首先将病毒代码段插入自动机，建出 fail 指针，显然如果能在不走串尾的情况下在字典图上经过一个环则有解，这一过程可以通过 dfs 实现。
考虑一个自动机常见优化，当一个节点的 fail 指针如果指向串尾，则其一定不能走。
考虑自动机的匹配问题，可以枚举匹配到的文本串末端，求出其在自动机上的节点编号后在 fail 树上用 DS 维护，由于 fail 树上根到节点路径上所有字符串都为枚举字符串的后缀，所以不重不漏。
考虑本题，建出自动机后，建出 fail 树，由于 fail 树上 \(u->v\) 路径表示 \(u\) 的字符串为 \(v\) 的字符串的后缀，说明新增一个模式串，在 fail 树上以其为根的子树一定能新增贡献，删除同理。查询只需要像上文一样，枚举末端，然后单点查询就可以了。
于是只需要用 \(dfs\) 序转序列问题后维护一个支持单点查询，区间修改的数据结构即可。
套路的建出 fail 树，由于修改权值，我们不能将 fail 树上以其为根的子树全部修改，因为其他串可以被权值更大的子串所覆盖，所以我们考虑转成单点修改权值。
查询的话同理，我们枚举末端，求出节点编号为 \(u\)，考虑到根到 \(u\) 上的路径全为子串，我们只需要求路径最值即可，可以用树剖来维护。
自动机 + DP
在自动机上的 DP 十分套路，一般设 \(dp[i][j]\) 表示跑到自动机上的节点 \(i\)，并且当前匹配到文本串第 \(j\) 位的答案。
正难则反，考虑完全不可读的文章数，则答案为 \(26^m-ans~\)。
有一个显然的结论是匹配到的点能计入答案当且仅当其不是串尾，于是可以直接用来做转移的条件。
记 \(dp[u][j]\) 表示跑到自动机第 \(u\) 个点，匹配到第 \(j\) 位的方案数。
初始值 \(dp[0][0]=1\)
当转移后的节点不为串尾时有转移方程 \(dp[tr[u].ch[i]][j+1]+=dp[u][j]\) 。
套路的，我们设 \(dp[u][j]\) 表示跑到自动机第 \(u\) 个点，匹配到第 \(j\) 位的方案数。
特殊的，我们在求 fail 指针时，以 \(u\) 为结尾的贡献要加上 \(tr[u].fail\) 的贡献，因为根到 \(fail\) 的路径组成的字符串为根到 \(u\) 路径组成字符串的一个后缀，当加入节点 \(u\) 时，后缀同样能累计贡献。
初始值 \(dp[u][j]=-INF\)
转移方程会比较简单：
\(dp[tr[u].ch[i]][j+1]=\max(dp[tr[u].ch[i]][j+1],dp[u][j]+tr[tr[u].ch[i]].sum)\)
将字符串建出自动机，标记串尾。
当把数位 DP 放在自动机上跑，根据套路，设 \(dp[u][j][0/1]\) 表示跑到自动机上第 \(u\) 个点，匹配第 \(j\) 位，前 \(j\) 位是否选取了上界（0/1）。
若当前处于第 \(j\) 位，位于节点 \(u\)， 且下一位不为串尾，则有转移：
\(dp[tr[u].ch[0\cdots9]][j+1][0]+=dp[u][j][0]\)
\(dp[tr[u].ch[n[j+1]]][j+1][1]+=dp[u][j][1]\)
\(dp[tr[u].ch[0\cdots n[j+1]-1]][j+1][0]+=dp[u][j][1]\)
初始值设置的比较特殊，我们考虑没有前导 \(0\) 的情况来设置初始值。
但是，这样不足 \(n\) 位的数会被我们所舍弃，所以我们在递推的初态要加上前 \(j-1\) 位全为 \(0\) 的情况。
标签：连边,tr,笔记,学习,fail,自动机,节点,dp From： https://www.cnblogs.com/tidongCrazy/p/16892132.html