边双连通分量概念：若在无向图\(G\)中，存在一个极大子图\(G'\)，使得\(G'\)中没有割边，则称\(G'\)为\(G\)的一个边双连通分量，记作\(\texttt{E-DCC}\)。使用场景：将无向图转化为一棵树（即无向图上的缩点）。求解步骤：确定割边，再遍历所有点且不经过割边，那么能联通的点都是即在同一

连通性问题点双连通:在无向图中，删除一个点（不是\(x\)或者\(y\)）后，点\(x\)和点\(y\)仍然能够彼此到达，那么称\(x\)和\(y\)是点双连通的。边双连通:在无向图中，删除一条边后，点\(x\)和点\(y\)仍然能够彼此到达，那么称\(x\)和\(y\)是边双连通的。性质点双连

割边在无向图中删了一条边后，图中联通块个数增加，则称该边为割边。判定对于一条\(cur\toi\)的边，若\(low_i>dfn_{cur}\)（不能取等，画图便知理由），则该边为割边。T103481&P1656板子。P1656code#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;intn,

DSUontree又称tree上启发式合并。适用于统计子树内信息。原理：贪心。特征：通常需要一个全局的桶。实现方法：对于每个节点，先统计「轻子树」并清空桶，再统计「重子树」并保留桶。其中，「重子树」表示每个节点最大的子树，其余则称「轻子树」。通常需要离线询问。正确性说明：类似

树上差分概述：擅长在树上一条路径上统计边或者点的信息。下文令差分数组为\(d_i\)，\(lca\)为路径两端点的LCA，\(fa_i\)为\(i\)的父亲。按边的差分将\(a\)到\(b\)的路径上的边权加\(val\)：\[d_a+val\tod_a\\d_b+val\tod_b\\d_{lca}-2\timesval\tod_{lc

庆祝该系列突破80期！！！1文中可能有彩蛋（记忆化搜索dp的一种dfs实现。P1434令\(dp_{i,j}\)表示以\((i,j)\)结束的最长滑坡的长度。答案：\(\max\{dp_{i,j}\}\)。初始：\(dp_{i,j}=1\)。转移：\(dp_{i,j}=dp_{x,y}+1\)，其中\((x,y)\)为\((i,j)\)四个方向上的邻接点。实现

IDDFS使用场景：搜索树非常大而答案的深度较浅，一般在\(20\)以内，且dfs会TLE，bfs会MLE。算法原理：以dfs的形式搜索；设定搜索的深度限制\(dep\)；dfs深度不能超过\(dep\)，且要恰好遍历所有\(dep\)的状态；若在\(dep\)层没有找到答案，\(dep+1\todep\)，重新DFS

P1775典。code#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=3e2+5;intn,a[N],sum[N],dp[N][N];signedmain(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; memset(dp,0x3f,sizeofdp); for(inti=1;i<=n;

常用dp状态：\(dp_i\)表示以\(i\)结尾的XXX/前\(i\)个元素的XXX。涉及的类型（由易到难）：线性dp，背包，区间dp，树形dp（换根dp），状压dp，dp的各类优化（数据结构优化、斜率优化、四边形不等式优化......）。背包问题：01背包、完全背包、分组背包、多重背包、树上背包。P1455并查

拖更了一个暑假。P6492很妙的线段树阿。对于修改，我们无需用lazytag，只要每次跑到叶子节点去直接修改即可。对于询问，答案即为树根的信息，因为它每次询问的都是整个区间。最难的是pushup部分：我们需要维护三个东西，ans,lx,rx，分别表示当前节点的整个串的最长合法串/左端点开

UVA1328简单题。我们有结论：对于一个周期串S的子串T，它的最小循环节即为T-nxt_{\left|T\right|}。（具体请查阅往期笔记）于是，我们枚举所有前缀，检验上式是否能被当前前缀的长度整除并且不止一个循环节即可。code#include<bits/stdc++.h>usingnamespacestd;constintN=

CF126B朴素解法：求出原字符串的最长border，并kmp匹配出出现在中间的最长border，若没有则不断缩短border的长度，直到中间存在。若border长度减到了\(0\)，则无解。我们通过画图来探索优化方式。如图，蓝色部分为原串的最长border，红色部分为蓝色部分的最长border。容易发现，

Kobe-Morris-Pratt算法定义一些基本定义：border：是一个字符串的子串（不与其本身相同）且满足既是其前缀又是其后缀的字符串，我们称之为该字符串的一个border。Kobe-Morris-Pratt算法（以下简称KMP算法），是解决字符串匹配问题的一种算法，实际做题中常偏思维，通常用到的只有其中的bo

众所周知，换根dp是非常套路的。换根真好玩（换根dp：当不同节点作为根时，dp结果不一致，若枚举每个节点作为根，则时间复杂度过高，在此种情形下，可使用换根dp处理相邻两节点间的贡献，从而达到快速换根的效果。使用场景：对于一棵树，寻找以某节点\(u\)为根时取得的最大值/最小值

登神长阶！P1272&P1273请查阅往期笔记，此处不再赘述。其中P1273我们学到了定义更好求解的状态（一般是转化为价值，如本题），再通过枚举求解最终答案。P8625容易发现你选出的\(S\)一定是一个子树。然后这题就变成最大子树和了。关于最大子树和那题，请查阅往期笔记，此处不再赘述。

复习树形dp。树形dp定义状态一般套路：令\(dp_i\)表示以\(i\)为子树的xxx（要维护的信息），可以有多维，但一定会有这一维。P2016&P2014请查阅往期笔记，此处不再赘述。P2585以前是分讨每个节点有几个儿子，然后分别转移。其实不用分讨，直接将所有节点视作有两个儿子，初始时将它

树上倍增：维护\(dp_{i,j}\)表示节点\(i\)向上移动\(2^j\)步所到达的节点编号、区间最值、区间和等信息。倍增求LCA：预处理：令\(dp_{i,j}\)表示\(i\)向上走\(2^j\)步所到达的节点。转移：\(dp_{i,j}=dp_{dp_{i,j-1},j-1}\)。初始：\(dp_{i,0}=fa_i\)。查询

RMQ问题/ST表：静态区间求最值。实现（以最大值为例）：倍增dp,预处理\(st_{i,j}\)表示区间\([i,i+2^j-1]\)内的最大值，我们有转移方程：\[st_{i,j}=\max(st_{i,j-1},st_{i+2^{j-1},j-1})\]相当于是把\([i,i+2^{j-1}-1]\)与\([i+2^{j-1},i+2^j-1]\)这两段区间的最大值拼了

HDU6567首先我们发现每棵树内部的距离已经固定，只有经过新边的路径才会产生贡献。又因为重心到树上所有节点的距离和最小，所以我们连接两树重心。然后我们想到一个经典套路：计算距离可以不枚举点，只枚举边。于是我们枚举每条边，计算出它们各自被经过的次数，再求和即为答案。维护\(

树的重心当\(u\)作为根时，其节点数最大的子树最小，则称\(u\)为树的重心。性质一：节点数最大的子树的节点数不超过\(\frac{节点总数}{2}\)。（反证法，若某重心\(u\)的节点数最大的子树的节点数超过\(\frac{节点总数}{2}\)，则将其一个子节点提起来会更优）性质二：至多两个且一

树的中心当选取树上节点\(u\)为根时，最长链最短，则称\(u\)为树的中心。性质一：至多\(2\)个且一定相邻。性质二：一定位于树的直径上。性质三：若一棵树有多条直径，则它们必定交于树的中心。性质四：树的中心为根时，根到直径两端点分别为最长/次长链。U392706板子。

树的直径：定义：树上两个距离最远的点形成的简单路径（不重复走一条边/点）性质：不唯一。树的直径的端点一定是度数为\(1\)的点。证明：显然。树的直径若有多条，则必交汇于一点，即中心。证明：首先每条直径只能交于端点（因为是一棵树，一个节点不能有两个父节点），然后此交点必定

退役选手复活后的第一篇。https://www.luogu.com.cn/problem/SP4033其实只要一个insert.就是插入时没新建节点\(\to\)自己是别人前缀，插入时途经了别人的结束节点\(\to\)别人是自己前缀。code#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+5,M=31;i

必考题四选一 Home&Accommodation选择高频考点的7个问题1.Whatkindofhouseorflatdoyouwanttoliveinthefuture?Well,currentlyIhavebeensharingaflatwithyoungcouple,andIhatethattheynevercleanupthekitchenafterusingit.Sointhef

\(\mathcal{TRIE}\)：用于存储和查询字符串的树形结构，相同前缀的字符串共用节点，每个节点存储一个字符。操作：insert：单次\(O(len)\)search：单次\(O(len)\)性质\(1\)：若一个字符串\(T\)作为前缀，则包含\(T\)的所有字符串的“终止节点”一定在以\(T\)的“终止节点”为根