Description给定一张\(n\)个点\(m\)条边的无向简单图。问图中能否找到两个点，满足这两个点之间有至少三条完全不相交的简单路径。\(n,m\le2\times10^5\)，图不保证连通。Solution容易发现有解地充要条件是存在两个环有边交，考虑在dfs树上做这件事。注意到非树边一定

D.网络攻防题意：一张无向图，求至多删除\(k\)条边使得图不连通的方案数。\(k\in[1,2]\)。首先考虑\(k=1\)，答案即为无向图中的桥边。预计得分\(15\)分。对于\(m\le2\times10^3\)的数据，我们可以枚举一条边删除，求剩余图中的桥边数量，最后加上桥边数量即可。预计得分\(30\)

poj3417题目其实很简单，如果知道树上差分是什么基本就是秒了。首先题面所说的，有\(n-1\)条边，保证两点之间只有一条简单路径，显然是树。剩下的边就是让这个树产生环的非树边。题面要求删除两条边，使之分为两部分，假如没有环状的结构，也就是没有那些非树边，就只需要随便删除一条边就可以

描述一个无向连通图，每个点\(u\)有点权\(w_u\)，处在\(u\)点时可以花费\(w_u\)的时间去任何一个距离\(u\)最短路径边数不超过\(f_u\)的点。现在，从\(1\)号点出发，对于每个\(1\lek\len\)，求出\(1\)到\(k\)需要的最小时间。\(n\leq200000\)\(m\leqn+50\)解决

桥桥是如果从图上删去这条边会使得这张图不连通的边。有两种方法1在图上任意一个环的边都不是桥,其他的都是。应为如果删去,儿子段和父亲段就不可达了。2首先,不在DFS树上的边肯定不是桥。如果一条在DFS树上的边不是桥\(\to\)它的子树内没有一个节点可以通过多条非

CF1555FSolutionlink分析一张图中的环，我们可以考虑把图表示为一棵生成树加上许多非树边。对于这题，我们考虑动态维护一片森林，在每次准备加一条边\((u,v)\)时：如果这条边加进去后与森林不形成环，那么它与图肯定也不形成环，那么直接加进森林中。如果这条边是森林的一条非树

TheShortestStatement给一张\(n\)个点\(m\)条边的无向连通图，保证\(m-n\le20\)，\(q\)次询问求两个点间的最短路。\(n,m,q\le10^5\)。由于边数只比点数多20，所以如果我们建出这张图的一棵生成树，那么非树边至多有21条。那么现在两点之间的最短路就转化成了不

题目链接考虑每条非树边的取值，显然不能小于等于该边与树边形成的环中的最大值（当然这条非树边也可以不存在），所以每条非树边的取值范围就是\(S-max(w)+1\)（\(+1\)的原因是该边可能不存在）。暴力枚举肯定会超时，考虑优化。发现\(kruskal\)算法获得最小生成树的过程中，按从小到

无向图的割点先给出几个定理：A：一棵树中的所有结点对于任意结点的可达性一致。记\(p(u,v)表示u和v可以相互到达\)。也就是说，如果G是一棵树，那么\(\forallu,v\inG,\forallk,p(u,k)\iffp(k,u)\)。B：一个无向图的DFS树中，对于任意一个非树边\((u,v)\)，\(u,v\)一定有祖先孩

前言记录一下，顺便捋一捋思路。前置知识最小生成树\(\tt{Kruskal}\)树上倍增\(\tt{LCA}\)非严格次小生成树有一种贪心的做法，我们先得出该无向图的最小生成树，最小生成树上的边称为树边，反之为非树边。先可以得到一个定理，次小生成树与最小生成树一定只有一条边不同，也就是次

1.有向图欧拉回路计数：欧拉回路与一颗\(1\)为根且非树边排列好的内向树形成双射。欧拉回路映射内向树：把最后一条边看做树边，剩下走过的看做非树边。内向树映射欧拉回路：能按顺序走非树边就先走非树边，最后走树边。于是答案是\(T_1d_1!\prod_{i=2}^n(d_i-1)!\)，其中\(T_1\)是

NoteTarjanPart1怎么做自己看书Part2为什么是对的证明：搜索树是一棵树由于每个节点都只会访问一次，回溯一次，故会访问(n-1)*2条边，只取访问时的边，即n-1条，可以构成树证毕。证明：在一个简单环上的一条边不可能是桥如果破除这条边，只能把环断成链，不会损坏连通性。证毕。证明

基本概念边/点割集：若边集\(E'\)使得割掉这些边之后\(u\tov\)不连通，则\(E'\)是\((u,v)\)的边割集。类似地定义点割集。边/点连通度：若任意\((u,v)\)的割集大小都至少是\(s\)，则\(u,v\)是\(s-\)边连通的。类似地定义点连通度。Menger定理：\(u\tov\)的边连通

pjudge题解虽然写了，但可能是bot写的，写的很不清楚。根据经典做法，搜出一棵dfs树，对非树边赋随机权值，树边权值为跨过它的所有非树边的权值xor。那割三条边能割开的条件就是：选三条边的一个子集，这个子集中的边权xor为0。也就是存在\(w_i=0\)或\(w_i\oplusw_j=0\)

[[AHOI2005]航线规划]([AHOI2005]航线规划-洛谷)首先是树的经典套路，依次删边\(\Rightarrow\)倒着加边然后问题就转化为了求两点间非环边的数量，且会不断加边一直缩点

对于一张图，若已经建出了一棵生成树，然后考虑一条非树边是否能够替换一条树边。结论就是一条非树边\((x,y)\)，只能替换树上路径\((x,y)\)上的任意一条边。二级结论，可以免

T1：算是一个小数学题，但是要一些大胆的想法，就是答案不会很大，直接暴力即可。PS：T1一般不会很难，如果感觉没思路可以尝试打表。T2：要求无权图最小环的数量，可以考虑环的求法，例

模拟赛20221115Tree|CQNK\(O(m*n*2^n)\)很好做，但是本题有更优秀的做法：在此记录复杂度\(O(n*2^n)\)的做法。考虑从后往前dp，设dp状态\(f_{s,0/1}\)分别表示在填

草稿：非树边\(u,v,[l,r]\)把\(u,v\)路径上所有边上界与\(r-1\)取个\(\min\)。剩下的边左端点排序后贪心，每次取右端点最小的一个元素。开始只考虑树边。当前加入一

考虑一个naive的做法，按照以是否为红边为第一关键字，\(id\)为第二关键字，顺次给权值。容易发现这种做法是不优的，因为非树边有可能\(id\)较小并且对后面的红边没有影响。

这东西显然比广义串并联图和cluster上的DDP不知道简单到哪里去了/fn首先回顾一下几个比较基础的定义：边连通度：两个点之间的边连通度就是它们之间的最小割大小，即，最小

动态图连通性再这样下去要被自己蠢死维护一副图，支持\(\operatorname{link,cut}\)，判断\(x,y\)是否在同一个联通块中最\(naive\)的就是每次双端\(\operatorname{b