这是仙人掌的模板题，仙人掌不能有自环，但是可以有重边。多颗仙人掌组成的图叫做沙漠。将仙人掌的每个环缩成一个点之后，就会形成树仙人掌转树要利用圆方树：①.任选一个点为根②.此时每个环有且仅有唯一一个点到根的距离最近。然后将环中的点分类，离根节点最近的点叫“头”，剩余的点作

定义割点：无向图中，若删除点及其连边，连通块变多，那么被删除的点为割点点双连通：若无向图中点对\(x,y\)，删除任意非\(x\)和非\(y\)节点后，\(x\)和\(y\)任然连通，陈\(x,y\)点双连通点双连通子图：无向图中的一个子图\(G\)，\(G\)中任意2点都是联通的，那么称\(G\)为原图的点双

前言圆方树学习笔记，从一道例题讲起。题目链接：Hydro&bzoj。题意简述仙人掌上求两点距离。题目分析为了把仙人掌的性质发挥出来，考虑将其变成一棵树。圆方树就是这样转换的工具。先讲讲圆方树的概念：原图上的点为圆点，每个点双对应一个方点，树边都是方点连向点双内的圆点。具

定义圆方树：将无向图转化为树形结构的数据结构，使得树上2点路径上的点都是原图的必经点。圆点：原无向图\(G\)中的点，仍然保留在圆方树中，称之为圆点。方点：将每一个点双连通分量新建一个“方点”。树边：每一个方点都向对应的点双内的圆点连边。基本性质：性质一：圆方树的总点数=

一些概念割点：无向图中，若删除点x及其连边，连通块变多，那么x为割点。点双连通：若点对x和y,删除任意非x和非y节点后，x和y仍然联通，称x和y点双连通。点双联通子图：无向图中的一个子图G，G中任意两点都是点双连通的，那么G为原图的一个点双连通子图。点双联通分量：无向图中的极大点双联通子图

圆方树大概分两种，一个是圆方树，一个是广义圆方树。圆方树这可以解决仙人掌上的问题。任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。很多题解将其作为无向图构建，本文将其构建为外向树，在这个问题中两种构建方式不会影响求解。构建方式记读入的图为原图，构建的

圆方树这里的圆方树指广义圆方树。对于一张\(n\)个点的无向图，其中包含\(k\)个点双，那么这张图建出的圆方树一共有\(n+k\)个点，其中前\(n\)个点为原图中的点，称为圆点，后\(k\)个点每个点代表一个点双，称为方点，每个点双与其中包含的点连边构成一个菊花，这\(k\)个菊花经由图

省流：因为一月底回厦门玩然后又回泉州过年，直到2.17才开始做题。[APIO2018]铁人两项圆方树和后缀数组我都想开个贴单独写。考虑关于“简单路径”，在点双上都有很特殊的性质。考虑把原图的圆方树建出来，然后考虑简单路径和圆方树的关系。注意到，在同一点双的两点的简单路径的并集，

圆方树学习笔记圆方树是优秀的图论算法，从仙人掌图向无向图扩展，利用割点和点双联通分量的性质，实现了图向树的转换。对仙人掌的处理：圆方树——处理仙人掌的利器而且实现十分简单算法思路前置知识割点和桥，点双联通分量。思路对于一个无向图，圆方树理解可以如下：原图中点是圆

今天学习了圆方树，并且做了一道和这道题很像的题，于是就又来做了一下这道题。题意给定一张不保证连通的无向图。求有多少个点对\((a,b,c)\)满足\(a\)到\(c\)的简单路径上经过了点\(b\)。思路显然圆方树。点双缩点过后构造一颗圆方树，然后考虑如何计算答案。圆方树有一个实

今天在做ABC318G这道题，要用到圆方树的知识，于是就去学了圆方树。学习圆方树首先需要学习点双连通分量以及缩点，此处不多赘述。圆方树中分两种类型的点：圆点和方点。圆点指的是原来的无向图中的所有点，而方点指的是每一个点双连通分量所代表的点。相当于每一个点双连通分量就是一个

圆方树，是解决仙人掌问题的实用方法，假设最初图都是圆点，对于每个环新建一个方点并连接这个环上所有圆点，能很好规避同一个点可能属于很多个环的情况，并且发现build完之后是一棵树广义圆方树，能够不局限于去解决仙人掌问题，能上升到无向图层面，很好解决图上路径类，等等问题那么如何建立圆

圆方树，是解决仙人掌问题的实用方法，假设最初图都是圆点，对于每个环新建一个方点并连接这个环上所有圆点，能很好规避同一个点可能属于很多个环的情况，并且发现build完之后是一棵树广义圆方树，能够不局限于去解决仙人掌问题，能上升到无向图层面，很好解决图上路径类，等等问题那么如何建立圆

圆方树的引入我们知道，图没有很好的性质，而树有很多性质，并且容易通过很多方式来维护树上信息，因此将图上问题转化为树上问题是我们想要解决的。圆方树就是将图转化为树的数据结构。圆方树的分类圆方树分为两类：狭义圆方树，广义圆方树。狭义圆方树狭义圆方树是可以用来将仙人掌图转

P9535「YsOI2023」连通图计数非常好题目，爱来自湖南。\(m=n-1\)等价于给定度数求树的个数，这是一个经典题，在「HNOI2004」树的计数有描述，即利用Prufer序列得到答案为\(\binom{n-2}{(d_1-1)(d_2-1)\ldots(d_n-1)}\)。\(m=n\)即基环树，对于整个大环建立一个虚点，该点向环上的所

为什么只写圆方树呢，因为点双代码比圆方树长一倍其实是因为边双可以被圆方树表示出来前言这里给tarjan中的low数组的定义明确一下，其代表的是包括自己在内的搜索子树内经过最多一条非树边能够到达的最浅节点边双这个很简单，如果有一个点的low值等于他的dfn序了，那它和栈

圆方树最初是处理「仙人掌图」（每条边在不超过一个简单环中的无向图）的一种工具，不过发掘它的更多性质，有时我们可以在一般无向图上使用它。个人觉得，圆方树是一个很好的工具。圆方树的题目更多的侧重于想，而不是怎么建圆方树。前置知识——点双连通分量点双连通分量：不存在割点的图。

A询问\(L\lei,j\leR\),其中\(\gcd(i,j)\not=1,i,j\)的对数。莫反先求出\(gcd(i,j)\not=1\)的对数，然后再直接调和级数暴力删去\(i,j\)是倍数的对数即可。BP4334[COI2007]Policija考虑建立圆方树。圆方树是怎么样的呢？圆方树是对于每个点双，都建立一个方点，然后

构建在将图变为树的方法里，圆方树与v-dcc类似。圆方树中，原来的每个点对应一个圆点，每个点双对应一个方点。故圆方树的节点数为\(n+c\)，其中\(n=|V|\)，\(c=|\text{v-dcc}|\).对于每个点双，其方点向这个点双里的每个点连边，形成一个菊花图，多个菊花图通过割点连接。割点的数量小

点双边双强连通拓展以及一些小技巧目录点双边双强连通拓展以及一些小技巧小技巧：1.关于割点：2.关于点双和边双的判断技巧：3.关于自己制造样例的技巧：例题：拓展知识1.广义圆方树：知识点：例题：bzoj3331小技巧：1.关于割点：点双常常存在割点情况，很难搞，每次dfs都很头疼（不知道割点在哪几个连通

圆方树前置知识：点双连通分量tarjan求点双对于一个无向图，在维护某些信息时可以利用圆方树的方法把原图转为一棵树来处理我们称在原图上的点是圆点对于每个点双联通分量，新建一个连向点双内所有点的新点，称其为方点点双内的所有点除了向方点连边以外不向点双内其他点连

day\(-n\sim-1\)上课卷点数据结构和树形dp，虽然不是板题不会做，但是还是学会了一些小trick。下课摆烂。day\(0\)摆了一天的烂，下午动员+板刷zxy游记，不过pty说的非常有道理，省选就是心态比赛，稳住心态就可以拿让人满意的分数。day\(1\)8：20左右坐到了位置上，试了下键盘，好不

概念圆方树是一种基于无向图构造的树。我们知道，圆方树最早是WC上提出的处理仙人掌的东西，用于将树上做法拓展到复杂度正确的仙人掌做法。但是一些关于点双有性质的题也

一些概念连通：无向图中的任意两点都可以互相到达。强连通：有向图中的任意两点都可以互相到达。连通分量：无向图的极大连通子图。强连通分量：有向图的极大强连通子图。DFS

圆方树学习笔记oiwiki模板voidtarjan(intu){ dfn[u]=low[u]=++ct;st[++tp]=u;tot++; for(intv:g[u]) if(!dfn[v]) { tarjan(v);low[u]=min(low[v],low