20200804 专题：仙人掌（圆方树）

仙人掌（圆方树）"/>

20200804 专题：仙人掌（圆方树）

总览：

无向仙人掌图的定义：
任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。

处理方法：
建立圆方树
圆方树的建点：

1. 原图中的点都是圆点
2. 对于每个点双连通分量，新建一个方点，这个方点和环上其它圆点连成菊花图
3. 对于不在环上的两个圆点，保留原图中的边

根据仙人掌的性质，易证不存在相邻的两个方点
边 ( u , v ) (u,v) (u,v) 权值的确定：

• 若 u , v u,v u,v 都是圆点，则权值为原图中边权
• 若 u u u 为方点，则权值为 v v v 到 u u u 父亲的最短路

感性理解：
对于图中每一个环建一个方点，环上的圆点与之连边
环与环间的边保持不变
方点与圆点间的边权为圆点到环的出边的距离

性质：
树上圆点的信息对应原图上的信息
树上方点的信息对应环上的信息

建树模板：

inline void build(int fa, int x, int len) {top = dep[x] - dep[fa] + 1;for (int i = x; i != fa; i = f[i]) st[top--] = i, len += dis[i] - dis[f[i]];st[top] = fa;top = dep[x] - dep[fa] + 1;SQT::cnt++;SQT::sum[SQT::cnt] = len;int now = 0;for (int i = 1; i <= top; i++) {int w = min(len - now, now);SQT::edge(SQT::cnt, st[i], w), SQT::edge(st[i], SQT::cnt, w);SQT::be[st[i]] = (w == now);now += dis[st[i + 1]] - dis[st[i]];}return;
}//方点-圆点
inline void tarjan(int fa, int x) {dfn[x] = low[x] = ++tot, dep[x] = dep[fa] + 1, f[x] = fa;for (int y = head[x]; y; y = road[y].nex) {int z = road[y].to, w = road[y].w;if (z == fa) continue;if (!dfn[z]) {dis[z] = dis[x] + w;tarjan(x, z);low[x] = min(low[x], low[z]);} elselow[x] = min(low[x], dfn[z]);if (dfn[x] < low[z]) SQT::edge(x, z, w), SQT::edge(z, x, w);//圆点-圆点}for (int y = head[x]; y; y = road[y].nex) {int z = road[y].to, w = road[y].w;if (z == fa) continue;if (f[z] != x && dfn[x] < dfn[z]) build(x, z, w);//取出环，建方点}return;
}//建树

T1 P4244 [SHOI2008]仙人掌图 II

思路：
找仙人掌直径模板
建树后 树形dp 即可
方点的儿子成环，不能直接转移，要先 环形dp 找出环上最短路
环形dp 可以拆环成链，复制一倍

代码：

#include <bits/stdc++.h>
using namespace std;
namespace IO {
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define ch()                                                               \(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) \? EOF                                                               \: *p1++)
inline int in() {int s = 0, f = 1;char x = getchar();while (x < '0' || x > '9') {x = getchar();if (x == '-'