仙人掌 && 圆方树 && 虚树 总结
Part1 仙人掌
定义
仙人掌是满足以下两个限制的图：
- 图完全联通。
- 不存在一条边处在两个环中。
其中第二个限制让仙人掌的题做起来十分舒服。
仙人掌的基环DP
首先勾出一棵有根生成树。
那么树边上正常转移即可。
我们把返祖边形成的环归到环上深度最浅的点上，即环顶。
那么到环顶时，单独跑一遍关于环的(DP)即可。
一般写法为：
void dfs(RG int u,RG int From) {
dfn[u] = low[u] = ++ oo ; fa[u] = From ;
for(RG int i = head[u] ; i ; i = t[i].next) {
RG int v = t[i].to ;
if(!dfn[v]) dfs(v , u) , low[u] = min(low[u] , low[v]);
else if(v != From) low[u] = min(low[u] , dfn[v]) ;
if(low[v] > dfn[u]) 正常的树形DP(F(v) --> F(u))。
}
for(RG int i = head[u] ; i ; i = t[i].next)
if(fa[t[i].to] != u && dfn[t[i].to] > dfn[u]) 基环DP(u,v)。
}
分清楚(low)、(dfn)的含义即可。
由于记录了(fa_u)，基环DP中的扣环也非常容易：
tot = 0 ;
for(RG int x = v; x ^ u; x = fa[x]) q[++tot] = x ;
q[++tot] = u ;
例题
例一：BZOJ4316 小(C)的独立集
题意：求仙人掌的最大独立集。
题解：做一遍正常的树形(DP)，遇到环则把环拉出来单独做一遍。
例二：BZOJ1023 SHOI2008仙人掌图
题意：求仙人掌的直径。
题解：
同样的做正常树形(DP)，碰到环顶则把环拉出来。
问题变为在环上选两个点，使其权值与距离和最大。显然单调队列即可。
Part2 圆方树
概况
圆方树是基于仙人掌的一种特殊数据结构。
其中圆点即图中原来的点，方点则代表一个点双。
我们沿用上面处理仙人掌(DP)的做法。
如果是生成树上的边，则直接相连。
否则，把环抠出来，为这个环新建一个方点，将环上的点与此方点连边。
板子与上面的仙人掌DP基本一样就不放了。
那么我们就可以在圆点上维护原本图单点信息，方点上维护点双信息了。
例题：BZOJ2125 最短路
题意：询问(Q)次，每次询问仙人掌上两点的最短路。
题解：
考虑建出圆方树，方点向圆点的连边 边权为此点到环顶的最短距离。
那么查询两点((u,v))时，我们求出其(lca)，然后讨论：
- 若(lca)为圆点，答案即为：(dis[u] + dis[v] - 2*dis[lca])
- 若(lca)为方点，则(u,v)的(lca)为一个点双。
- 此时倍增找到(u,v)的点双进入点(u',v')，再求(Dist(u',v'))即可。
Part3 广义圆方树
概况
对于任意图，类似圆方树，可以建立出广义圆方树。
广义圆方树与圆方树的差别在与，特别的，对于两个点的联通量，也建立一个方点。
所以广义圆方树上只有圆-方边。
建立的方法与普通圆方树建法还是有所不同：
void Tarjan(int u,int From) {
low[u] = dfn[u] = ++ oo ; stk[++Top] = u ;
for(int e = G1.head[u] ; e ; e = G1.t[e].next) {
if(e == (From ^ 1)) continue ;
int v = G1.t[e].to ;
if(!dfn[v]) {
Tarjan(v , e) ; low[u] = min(low[u] , low[v]) ;
if(low[v] >= dfn[u]) {
G2.add(++N , u) ; int x = 0 ;
blg[N] = sum ;
do {
x = stk[Top] ;
G2.add(x , N) ; Top -- ;
}while(x ^ v) ;
}
}
else low[u] = min(low[u] , dfn[v]) ;
}return ;
}
特别要注意重边的问题(原图中不能有重边或自环)，同样时刻分清(low)、(dfn)的作用即可理解。
例题
BZOJ3331
题意：给定一张图与一些点对路径，对于每个点，求出必须经过此点的点对路径的数量。
题解
把广义圆方树建出来，那么一个点对路径上必须经过的点即圆方树上对应路径的圆点。
直接在广义圆方树上差分一下就行了。
UOJ30 Tourist
题意：给定一张图，两种操作：修改点权 或者 询问两点路径上的点权最小值。
题解
首先把广义圆方树建出来，考虑用方点维护(SCC)中的点权最小值。
但是这样建的话，修改一个圆点时需要把与其相连的方点全部修改一遍。
这很容易被卡成(O(n^2))。
所以对于方点，我们不维护对应的环顶(即广义圆方树中方点的父亲)。
这样修改的时候，我们就只用修改父亲。
查询时，如果两点的(lca)为方点，额外与(lca)的父亲(环顶)取(min)即可。
[APIO2018] 铁人两项
题意：求有多少点对((s,c,f))，满足存在一条u -> c -> f且路每个点只经过一次的路径 的个数。
题解
显然枚举一下(c)，然后算它的贡献。
考虑广义圆方树上从一个圆点出发的不重复路径有哪些。
除了普通的树上路径外，还可以在与此点处于同一个方点的那些点中选出两个。
这个好像DP一下就行了？
两遍dfs，第一遍考虑儿子的贡献，第二遍考虑父亲的贡献。
大力讨论一下，第二边dfs的时候记得删去当前子树的贡献，简单转移就行了。
Part3 虚树
概况
其实与上面的图论没有半毛钱关系......
虚树是指在原树上选出一些点构出一棵新树，并保证新树与原树形态、性质相同。
一般来说，对于多组询问，若 (sum) 点数 较小，
那我们不如对于每次询问构出虚树，然后就可以(O(n))进行DP啦。
实现
其实比较简单，注意父子关系的保持即可。
首先对原树进行一遍(dfs)搞定所有点的 (dfs)序(dfn) 与 子树结尾(ed) 。
那么对于每次询问，我们把这些点抠出来，然后：
- 按照(dfn)从小到大(sort)。
- 把相邻两个点的(lca)加入点集中。(因为保持树的形态需要这些点)
- 把 根结点 加入点集中。 (为了使最后的虚树联通)
- 按照(dfn)再进行一遍(sort)。
- 维护一个(dfs)顺序的栈，时刻保持栈顶结点为当前入栈点的父子关系。
- 把入栈点与栈顶连接(前提是栈顶存在)，然后把入栈点入栈。
- 重复以上操作直到所有点入栈，此时虚树构建完成，虚树的根就是原树的根。
代码如下：
IL bool cmp(int a , int b) {return dfn[a] < dfn[b] ; }
IL void Build(){
dfs(1 , 0) ; //求 dfn 与 ed
get_query_node , put it in 'p[]' .
sort(p + 1 , p + n + 1 , cmp) ;
for(int i = 1; i < n; i ++) p[i + n] = LCA(p[i] , p[i + 1]) ;
p[2*n] = 1 ; n = n * 2 ;
sort(p + 1 , p + n + 1 , cmp) ; Top = 0 ;
for(int i = 1; i <= n; i ++) {
while(Top && ed[stk[Top]] < dfn[p[i]]) -- Top ;
if(Top) G2.add(stk[Top] , p[i] , E<stk[Top],p[i]>) ; stk[++ Top] = p[i] ;
}return ;
}
虚树上的边压缩了原树上的路径信息。
特别注意，由于我们会在虚树的边上压缩信息以供后续处理，
而我们为了保证虚树联通所以可能额外引入了原树的根。
所以一定要考虑额外引入点对答案的影响，若有影响，则要删去其贡献！(高频错点)
例题
以下题目的通性：多组询问，总点数 (leq) (n)。
[SDOI2011]消耗战
题意：一棵树，边有代价，每次询问要求删去最小代价的边集，使得关键点不能到达根结点。
题解：
每次询问建出虚树，考虑如何(O(n))进行(DP)。
貌似记录一下子树内有无关键点，然后一路向上选择切掉当前边或累加儿子子树最优解即可。
[HEOI2014]大工程
题意：
一棵树，边有边权，每次询问给出(K)个点，在它们之间修(inom{K}{2})条边。
每次要求回答三个问题：(1)最长路 ; (2)最短路 ; (3)所有路径的长度和是多少。
题解：
每次询问建出虚树。
最短路最长路基础的直径DP即可。路径长度和考虑一下经过这条边的点对数就行了。
特别注意最短路与最长路DP时，
起点与终点位置只能是询问点(不能是引入点)，这个每个点附初值时特殊处理一下就行了。
[SDOI2018]战略游戏
题意：一张图，每次询问给定点集，问有多少个点满足删去后使得点集中任意两点不联通。
题解：
看到图上连通性问题直接上圆方树(那是什么？上面就有......)
把圆方树建出来，然后再建圆方树的虚树。
那么答案就是"虚圆方树"上除了询问关键点外的圆点个数，直接建树是统计即可。
[HNOI2014]世界树
题意：
定义原树上的一个点被其离的最近的关键点管辖。若距离相同则选择编号小的。
对于每次询问，给出一些关键点，试输出每个关键点管辖的点的数目。
题解：
首先把关键点建出虚树。
那么我们是可以O(n)DP出这些点的归属是吧。
这是经典的DP了，两遍dfs，第一遍DP出儿子最优值，第二遍再考虑父亲。
然后考虑哪些没有在虚树中出现的点(都压缩在边上)。
对于虚树上的边，我们分情况讨论：
若边的两端被同一个点管辖，那么显然这条边上所有的点都归那个点管辖。
如果两端的点被不同的点管辖，那么一定存在一个分界线。
我们可以倍增二分找到那个分界线，然后给两个关键点加上对应贡献即可。
CF809E Surprise me!
题意：
给定一棵 (n) 个节点的树，个点有一个权值 (a[i]) ，保证 (a[i]) 是一个 (1..n) 的排列。
求 $$frac{1}{n(n-1)}sum_{i=1}^nsum_{j=1}^nvarphi(a_i)·varphi(a_j)·dist(i,j)$$
其中， (varphi(x)) 是欧拉函数， (dist(i,j)) 表示 (i,j) 两个节点在树上的距离。
题解：
首先欧拉函数有个公式：(varphi(a*b) = varphi(a)varphi(b)frac{d}{varphi(d)})，其中(d=gcd(a,b))。
所以式子化一化？
考虑后面这一坨东西：
一种莫比乌斯反演既视感啊.....定义：
那么(f(d) = sum_{d|i} mu(frac{i}{d})F(i))。怎么求(F(d))？
貌似如果能(O(n))求那么总复杂度就是调和级数啊？
所以枚举(d)，然后把满足(a_i = kd)的点拿出来进行虚树DP。
维护一下子树内的(sum varphi(u)) 与子树内的(sum dep_uvarphi(u))，然后在(LCA)处统计答案即可。
后记
终于写完啦(QwQ)。
写了这么多，就是为了证明学了这些毒瘤玩意后我还活着......