圆方树 (Block-Cut Tree)

1. 核心定义与代数性质

圆方树是将无向图关于点双连通分量（v-BCC）进行结构分解所构建的等价树形结构。

1. 点集划分：

• 圆点（Round Node）：原图节点，编号范围 $1\sim n$。
• 方点（Square Node）：每个极大点双连通分量抽象出的代表节点，编号从 $n+1$ 开始递增。
• 节点规模：若原图连通，方点数至多 $n-1$，总节点数 $|V_T|\le 2n-1$。树相关数组必须严格开设 $2N$ 空间。

2. 拓扑性质：

• 二分图结构：圆方树不存在圆-圆边或方-方边，仅存在圆-方边。
• 从属关系：方点连接其所在点双包含的所有圆点；圆点连接所有包含该圆点的方点。

3. 割点与连通性判定：

• 原图割点充要条件：该点在圆方树中的度数 ${\mathrm{deg}}_T(u)\ge 2$。
• 原图非割点充要条件：${\mathrm{deg}}_T(u)=1$（仅属于一个点双）。

4. 路径等价定理：

• 必经点：原图 $u$ 到 $v$ 的所有简单路径的公共点集合（必经点），严格等价于圆方树上 $u\to v$ 树上简单路径上的所有圆点。
• 简单路径并：原图 $u$ 到 $v$ 所有简单路径经过的节点并集，严格等价于圆方树上 $u\to v$ 树上路径所经过的所有方点所管辖的圆点并集。

---

2. 构造算法 (Tarjan 点双维护栈)

在 Tarjan 求解点双的过程中，利用一个节点栈维护当前搜索子树中的节点。

核心状态转移与弹栈逻辑

1. 访问节点 $u$，记录时间戳 dfn[u] = low[u] = ++timer，并将 $u$ 入栈。
2. 遍历邻接点 $v$：

• 若 $v$ 未访问：递归搜索 $v$。回溯时更新 low[u] = min(low[u], low[v])。

• 若满足判定条件 low[v] >= dfn[u]：

• 触发新点双生成，创建方点 sq = ++tot。

• 圆方树连边 $(u,sq)$。

• 循环弹出栈顶节点 $x$ 并建立圆方树边 $(x,sq)$，直至弹出 $v$ 为止。

• 关键不变量：点 $u$ 不得出栈，因割点可同时属于更高的点双。

• 若 $v$ 已访问且不为直接树边反向边：更新 low[u] = min(low[u], dfn[v])。

---

3. 模板

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100005;

int n, m, tot;
vector<int> g[N];          // 原图邻接表
vector<int> adj[N * 2];      // 圆方树邻接表 (开 2N)

int dfn[N], low[N], timer;
int stk[N], top;

inline void add_tree_edge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u;

    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                int sq = ++tot;
                add_tree_edge(u, sq);
                do{
                    add_tree_edge(stk[top],sq);
                }while(stk[top--]!=v);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void build_bct() {
    tot = n;
    timer = top = 0;
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
            if (top > 0) --top; // 弹出孤立根节点
        }
    }
}

4. 经典模型与解题范式

模型一：两点间路径割点 / 必经点查询

• 数学映射：求 $u\to v$ 的割点数量。
• 解法：
• 圆方树点权赋值：圆点权值设为 $1$，方点权值设为 $0$。
• 查询 $u\to v$ 路径权值和，剔除端点 $u,v$ 自身（若端点不算割点）：

$$\text{CutVertexCount}(u,v)=\text{dist}(u)+\text{dist}(v)-2\cdot \text{dist}(\text{LCA}(u,v))+\text{val}(\text{LCA}(u,v))-2$$

• 复杂度：预处理倍增/树剖 $O(n\log n)$，单次查询 $O(\log n)$ 或 $O(1)$（RMQ LCA）。

模型二：动态点权修改与路径最值

• 数学映射：支持单点修改原图点权，查询 $u\to v$ 任意简单路径上经过节点权值的最小值。
• 复杂度陷阱：若圆点连接多个方点（菊花图割点度数达 $O(n)$），修改单点若暴力更新所有相邻方点，单次退化至 $O(n\log n)$。
• 优化策略：

1. 定根圆方树（以 1 为根）。
2. 每个方点用 std::multiset 仅维护其子圆点的权值集合，不维护其父圆点。
3. 单点修改：圆点 $x$ 仅需从其父方点的 multiset 中更新自身，修改代价严格 $O(\log n)$。
4. 路径查询：树链剖分查询线段树区间最小值。若 $u,v$ 的 LCA 为方点，该方点未统计其父圆点的值，需额外将 $\text{val}(\text{parent}(\text{LCA}))$ 加入最终结果取 $min$。

模型三：三元组简单路径计数

• 数学映射：在无向图中统计有序三元组 $(u,v,w)$ 的数量，使得存在一条简单路径依次经过 $u\to v\to w$。

• 容斥赋权法：

• 对于固定的端点对 $u,w$，$v$ 的可选数量等于 $u$ 到 $w$ 所有简单路径的点集并大小减 2。

• 根据圆方树路径性质，赋权规则：

• 圆点权值：$-1$（割点在相邻两方点中被重复计算，通过 $-1$ 抵消重复贡献）。

• 方点权值：$|V_{BCC}|$（该点双内的点数，即该方点的度数 ${\mathrm{deg}}_T(sq)$）。

• 任意两点 $u,w$ 间的合法中继点数即为圆方树路径权值和。

• 树形 DP：统计每条树上路径经过的次数，转化为每个节点的贡献乘上经过该节点的路径条数，全图 $O(n)$ 线性完成。