点双联通分量：对一张图，若其不含割点，则其为一个点双。1，对于点双中的两个点（除只有两点一边的特殊图），可以视作其必然存在两条不同的简单路径，使两者经过的并集为空。2，对于点双中任意一对点，经过它们的简单路径的并集一定为点双本身，意即可以认为两点间简单路径可以通过点双内任意一点。

T1邦布照相[贪心]Description给定长度为\(n\)的序列和一个\(k\)，在序列中找到字典序最小的且是\(k\)的排列的子序列，输出答案。\(k\len\le2\times10^5\)。Solution考虑贪心，遍历序列，用一个类似单调栈的东西维护答案，如果这个数在栈中出现过，便跳过，如果没出现过，先把栈顶

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

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

哈夫曼树定义带权路径长度：结点的权值乘以结点到跟的距离。树上所有结点带权路径长度之和最小的二叉树称为哈夫曼树。性质哈夫曼是满二叉树。来自维基百科：原序列构成哈夫曼树的所有叶子结点。离根结点越近，点权越大。非叶子结点的点权之和就是所有叶子结点的带权路径之和

$\quad$圆方树练手好题。$\quad$大概意思就是给你一个仙人掌，其中每个点都有点权。有\(m\)次询问，其中有两种操作：回答两点间所有可能路径（不重复经过一个点）上的点权最小值、将某个点的点权改为某值。$\quad$对于路径上点权最小值，可以先转化为圆方树，然后树链剖分解决，用方点

首先考虑这个\(S,T\)肯定需要固定一个算另一个的方案数。如果固定\(S\)，会发现非常不好给\(T\)下限制。于是考虑固定\(T\)，对\(S\)计数。首先考虑如果\(T\)只有\(2\)个点\(x,y\)，该怎么对\(S\)计数。考虑到这个简单路径的定义是不经过重点，考虑找到点双。然后能

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

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

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

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

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

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

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

7/11PRO-ProfessorSzu题意：给定有向图，有重边有自环，从\(1\simn\)中而每个点出发到达\(n+1\)不同的路径数，问那些点的路径数最多（重边算不同边，自环算不同点）。如果路径数大于36500，输出"zawsze"。先缩点，再拓扑。设\(f_{u}\)为这个强连通分量里的点的答案，如果强连通分量里的

P3436[POI2006]PRO-ProfessorSzu求scc后变为DAG，随便dp就好了。吐槽数据不对题面，细节巨多。但是肯定不够紫题。P3469[POI2008]BLO-Blockade500年前就做过了，又写了一遍，用了圆方树逃课。就是树上经过每个点的路径数量。P2860[USACO06JAN]RedundantPathsG好题。边

集训模拟赛的题解应该都在CWOI杂题里。主要就是题目的记录？不太想写游记。简单题不会写。7.7考试，考得依托。7.8很趣味的数据结构！感觉很有集训那味啊，就是前面讲一会简单的东西然后突然上强度。gym100739E.LifeasaMonster还是挺简单。套路地把切比雪夫距离转成曼哈顿

二分图最小点覆盖对于一般图显然有最小点覆盖大于等于最大匹配，这是因为每个匹配边都至少需要一个点来覆盖而根据konig定理可以证明二分图最小点覆盖等于最大匹配证明方

部分内容参照了OI-wiki定义对于这样的一个无向图，左侧的\({1,2,3}\)和右侧的\({3,4,5}\)分别构成一个点双联通分量。中间的\(3\)号节点就是一个割点。不难发现，点双

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

\(\mathscr{A}\sim\)遗忘十字路  Cover:「CF1746D」PathsontheTree.  Tag:「C.性质/结论」  最原始的思路自然是DP.令\(f(u,k)\)表示从\(u\)开始向子

CF487ETourists带权无向图\(N,M\)，\(Q\)次询问\(s,t\)所有不经过重复点可能路径经过的最小值的最小值。CODE每次修改一个圆点\(u\)周围的方点有点难。可是李神

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