题目求的就是点仙人掌的数量；点仙人掌的所有环缩点之后就变成了一棵树，于是考虑无根树的数量怎么求，很显然利用Prufer序列就好了；然后考虑怎么将Prufer序列移植到点仙人掌上面，此时就要利用扩展Prufer序列扩展Prufer序列：对于一个点仙人掌来说，先将所有环缩点变成一棵树，然后将所有缩点离

仍然建出圆方树，方点与原点之间的边权与上一道题目一模一样考虑普通的树怎么求树的直径：利用树形DP；于是尝试在圆方树上用树形DP。如果根是圆点，那么我们需要求解形如下图的直径按照我们之前建的边权，像普通的树形DP一样转移就好了如果根是方点，那么我们需要求解形如下图的直径于

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

法一：环套树。把基环树看作一个环上吊了几棵树，在处理时遍历环上每个点，处理出每棵树的答案，然后做环形的操作。缺点：只能处理基环树，如果是仙人掌就不适用了。法二：树回边。以深搜树的方式看待，用处理树的方式（比如树形DP）。在遇到环上深度最浅的结点的时候，让它把下方的环的结果当作一

基础定义图图\(G\)是一个有序二元组\((V,E)\)，其中\(V\)成为点集（\(Vertices\)\(Set\)），\(E\)称为边集（\(Edges\)\(set\)）。有向边、无向边如果边有方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的有出边和入边之分。相反，边没有方向的图称为无向图，即所有边都

题解建出原图的圆方树。由于原图无重边，不妨把桥看作二元环建树，这样圆点只与方点直接相连。圆方树定某一圆点为根后，若点\(u\)是圆点，定义点\(u\)的子仙人掌为点\(u\)子树中的圆点在原图的导出子图，定义该子仙人掌的根为点\(u\)；若点\(u\)是方点，定义点\(u\)的子仙人掌为点

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

GoodbyeSouvenir我们定义数字\(x\)在\([l,r]\)出现的最后一次位置减初始位置为该数字在\([l,r]\)内的权值。现在让你支持：单点修改询问\([l,r]\)中数字权值和。注意每个数字只贡献一次。tag：CDQ分治，贡献转化注意到每个数字只贡献一次，可以想到将每个数字的权值进

昨晚管神讲太晚了所以咕到8.8来写了上午博弈论和杂题，依旧听不懂

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

图的概念图：点--边度->有向图（入度，出度）||无向图（度）自环：若一条边的两个顶点为同一顶点，则此边称作自环。路径：从任何一个点出发，随意在图上走，走出来的序列叫路径。|简单路径（一条路径，每个点最多只能走一次） 特殊的图1）没有环的无向图：树-->无向，连通，无环  ||n个点n-1条边只有

据说是NP问题。很明显我们要先预处理出来勾股数对。但由于数过于大，所以常规的枚举是解决不了问题的。但也貌似没有什么很好的办法可以立马找到一个数的勾股数对。所以

牛客CSP-S提高组赛前集训营2预估得分:100+100+40实际得分:65+80+40不开longlong见祖宗T1服务器需求https://ac.nowcoder.com/acm/contest/1101/A小多计划在接下来

一.定义任意一条边至多出现在一条简单回路的无向连通图。二.思路给定一仙人掌图，多次询问两点最短距离。首先，如果是一棵树，是很好处理的，\(dis=d[u]+d[v]-2*d[lca]\)。然

题目链接2752.仙人掌图如果某个无向连通图的任意一条边至多只出现在一条简单回路（simplecycle）里，我们就称这张图为仙人掌图（cactus）。所谓简单回路就是指在图上不重复经过

题目链接2863.最短路给一个\(N\)个点\(M\)条边的仙人掌。仙人掌定义如下：任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。有\(Q\)组询问，每次询问

E.CactusWallMonocarpisplayingMinecraftandwantstobuildawallofcacti.Hewantstobuilditonafieldofsandofthesizeof$n\timesm$cells.Ini

title:无向图里找奇偶环-OI回忆录tag:DPdescription:https://codeforces.com/gym/103931/problem/J我退役后打ACM，当时队内每周vp训练，我寻思着调场水一点的就

你是什么仙人？引入仙人掌是一种特殊的无向图，它的任意一条边至多只出现在一条简单回路（每个点只出现一次的回路是简单回路，特殊地，自环不算简单回路）。这里借用一下[SHOI2006

同学们都会树的定义了吧，那么接下来我们来学习圆方树吧圆方树基础理论圆方树，适用于仙人掌上问题，可将仙人掌转化为普通树。将仙人掌上的点双连通分量合成一个方点（tarjan），